Fred,
Tile-based is like "Legend of Zelda" or graphical "nethack" They are basically 2D or 2.5D games where the background is like the ground and repeats with the same image.
You could set up a map in a 2 dimensional array with different numbers representing wall tiles, floor tiles, etc.
It allows you to use the same images over and over again to build the maps. The character can then traverse from tile to tile to move around.
Lloyd,
Developing Games in Java is a good book, but not much on the types of games you've mentioned. Beginning Java Game Programming is okay, the Headfirst Java book is great, but that's more Java than game programming, Killer Game Programming in Java is really good too. I think you might want a combination of the books though.
You might want to think outside tiles though. The reason I say that is because you can paint yourself a decent sized background image or a few of them and have them drawn on the screen, pieced together and it would probably look a bit nicer than smaller repeated tiles. It's the same thing but with larger tiles. Basically all you are doing in a tile game is drawing each tile to the screen or window first, since it's the background, then drawing the characters and enemies afterward.
Good Luck!
Brad