Hexcrawling is simply a must if you want to explore the unknown lands of your imagination! I do hexcrawling a little different then most. I squarecrawl! I do squares because it's easier to draw squares then it is to draw hexes. Plus I love the look of a blocky map, I blame it on playing too many NES rpg's...
I use 6x6 Tales as my base, I only use it's way of drawing the terrain. Instead of doing a totally square map, I start by drawing up a blocky island to make its shape a bit more interesting.
For generating the terrain I use Wilderness Hexplore which has a nice, simple weighted D20 table. If you just want to do traditional hexcrawling, this is the only resource you'd ever need. Also, both of these are totally FREE!
Roll an encounter check for the hex on a d6:
1.We found a cool area!
2.Signs of/ Indications of an area nearby cool area
3.Odd weather, environment event or a natural obstacle / a hardship to overcome
4.Nothing to see here
5.Signs of a critter/critters are/were near. Spoor/tracks
6.A critter/critters