Back to the original question, it depends on what format and how big (resolution/detail-wise) the photo is.
If it's a bitmap (.bmp), that's half the problem. A 'decent' sized photo will _easily_ reach into the megabytes. It is completely uncompressed.
More friendly formats:
.png - similar to .bmp in that no quality is lost by converting to this format. Uses loss-less compression (similar to how zip compresses files). Usually a 'medium' file size (and just a fraction of a bmp).
.jpeg/.jpg - probably the most popular image type. It compresses with a lossy compression (data is thrown out) to reduce the file size (this is similar to how mp3 compresses audio). With jpeg, you can sometimes notice 'artifacts' that weren't in the original. Usually this is kept low and you can get decent quality with this format. File sizes are usually small/medium.
.gif - uses a different type of lossy compression that jpeg does. I believe this one reduces the number of colors used in the picture, resulting in a way to store the data smaller. This is usually used best with graphics (clip art, smilies, web graphics, etc). It can be used with pictures, but sometimes you can get some funky results. Usually a small file size.
The only other thing that determines is the picture's resolution (and related, it's complexity). If the picture is large and complex, and you want to get it down to a decent size without completely destroying it by uber-compressing it with, say, a _very heavy_ jpeg compression to get it down to size, then compromise -- size it down a bit and then don't use such a heavy compression rate with jpeg (or try png and see where that gets you if you like).
Also, sometimes cropping can help cut out the 'extra stuff'. Even MS Paint can crop photos. Select the area you want, cut it out, and paste it as a new picture.
Might be worth it to check out Gimp (it'd likely be overkill though). Gives you access to compression rates of files though, as you save them.