I am designing a game that is working on a classic tile engine, but whose world is generated randomly. Are there existing games or algorithms that do this? The procedural generation algorithms I have found are never using a tile system... What would be the best way to generate a whole "world" using a tile system? I am not talking about mazes of blocks, but an overall "world map" thanks
Your question leads you into the field of procedural content generation.
Tile-based world generation derived from continuous/analog methods
By continuous, I means something that is not tiles, something that is analog, an example being a vectorised map. You can use any continuous technique for generation, and then quantise it. For example generate a high resolution Perlin noise image, then reduce it's resolution to fit your tilemap size, and sample the pixels to provide yourself a heightmap. (Heightmaps can be a great starting point for your world.) This because you mentioned seeing sources that didn't show you what to do in regards to how to apply it to tiles.
Tile-based world generation using a "blinkered" carving approach
With a tile (cell) based approach, you can do a sort of a blind generation where you generate the world bit by bit without looking further than eg. the directly neighbouring tiles, but this tends to look like the work of an insect. This is typical CA (cellular automata) stuff, and displays little larger scale intelligence.
Tile-based world generation using a broader world view, top-down
This takes a more intelligent approach to building the world tile by tile, since it will first build it region-by-region. In this way you get control over eg. different biomes, political regions, etc. as Tarn Adams has done in Dwarf Fortress. Of course this requires you to think a bit about how you would like to divide up your world. There are many ways, you will have to do your own research.
Procedural content generation is a pretty broad topic, so you'll need to do a good amount of reading before getting a solid idea of what it is you really want and how to go about it -- the devil is always in the detail. For that reason, some good sources for this are the rec.games.roguelike.development mailing list (a ton of information on tile based procedural worlds), AmitP's game programming pages (look under "Other Topics"), the Game Programming Wiki and last but not least, the Procedural Content Generation Wiki.
Procedural generation is an immense topic. How deep are you willing to go?
Nick Wiggill's answers are top-notch. I'd add to that by suggesting that you look at some mathematical methods of creating coherent random terrain.
Perlin noise offers a great way to create smoothed randomness, and works great for all sorts of terrain. Simulating erosion can give a realistic impression of height (although you may not need that since you're doing a tile-based game)
A lot of the techniques discussed in papers like this one by Oddlabs, makers of the Tribal Trouble, work well in 2D and at low resolutions, too. If you're more comfortable with this kind of approach, learning these techniques may be worth your while.
Spelunky's Procedural Space - a great introduction to procedural content generation by Darius Kazemi
Spelunky is a 2D game by Derek Yu that has some great Procedural levels.
There's also a procedural content wiki http://pcg.wikidot.com/