In Photoshop, make the images the height/width that they need to be to look good and yet fit most browsers. I like to make mine somewhere around 800 px wide (or tall). On my current site, they are no more than 640px wide (or tall) to make room for the navigation bar.
So, resize your images.
Next, if you're using any version of Photoshop 7 or better (including Elements 3) there is a thingie underneath your Save, Save as... dialogue under File that's called Save for Web. Click on that. It's super good at getting rid of extra color information and therefore making your files smaller so they load faster. This is the compression part.
I would use JPEG (.jpg) at High Quality (which is probably around 60-80%, whatever looks good—and the image viewer will show you a preview of the picture with those compression settings you're specifying so make it look nice, but watch the file size and try to keep it around 200KB).
That's pretty much it. Once you're satisfied with your preview image, just save it to whatever your image directory is for your website. Just don't save over your original file. That would kinda suck.
Take a look at my website/gallery thingie and you'll see what I did. No photo is over 640 pixels wide or tall and the file sizes are about 100KB.
Also, if you're doing thumbnails, find out how small you want them and make those thumbnails that size... that way they are super tiny and download super fast. I can wait a few seconds for a high res image to download, but not for a hundred thumbnails which are actually just the high res images scaled down in the browser.
Also, thumbnails don't need to be super high quality so you can just save them as regular JPEGs at medium compression and that'll work just fine. Just be sure you're saving them in the thumbs folder and not in the images folder where your big images are. Otherwise, folks will just be staring at thumbnails all day with a ton of dead space.
Hope this helps.