I did this on Photoshop 7. I'm not sure if it works on other versions but my guess is that it would work for Photoshop 6 (and maybe 5) as well.
The above are examples of the original and result. The result doesn't look that great but they can look good if you choose the right photo and spot to select. With that said, you will end up with something like the above.
First, take a picture and note the size. For simplicity's sake, we'll use the example photos as a guide. The size of the original is 300 x 212. You want to open a new file and increase the height (or width if you choose to have it extend that way). I opened a new file at 300 x 362. Then you paste your picture onto the window. Make sure it's placed on the top leaving blank space on the bottom for the extension. Then, take the single row marquee tool (this is the top left tool but you need to switch from the default rectangle marquee tool to this one. Then, select a part of the photo that you'd like to extend. I chose the very bottom piece. One you've selected it, you press CTRL + T. Then bring down the area to the area you want it extended to. Then VOILA! You're done!
//[back]