The images it produces are simple heightmaps that look very much like...well, ARE...fractal noise. I won't go into detail with the algorithm, but it basically interpolates between points a bunch of times with some controlled randomness. You can read more about it here, but I get better results from my program than the Wikipedia images show (sample below). To get a coastline, take the sample image and do a basic threshold operation on it. I also have programs that create an island surrounded by water and add an ocean to an existing heightmap.
I kind of want to post the code on this site, but it is not in any way a finished product. You would have to be able to compile and run it on your system.
As for the rivers...actually, after my earlier post, I created a new program that hopefully will be the groundwork of later river functionality. It can trace multiple rivers across the terrain the way real rivers would go. It's still a long way from being integrated into the main program, though.
You can't set a general shape for the terrain and then have it fractalized (though that would be a useful extension to add), you just take the initial shape and add oceans, lakes, whatever. My Edelu map's coastline was generated like that; then I just added in landforms according to my liking.