Phew... big question. If I was starting photography today, I'd borrow books from the library - to get some of the theory - and badger someone who takes decent pix to 'walk' me through the basics... in as simple a way as possible. Then I'd look for a beginner's camera and shoot, shoot, shoot...
Photoshop (or Photoshop Elements) has a "resize image" command that works very well. The default "bicubic smoothing" option will do a very good job when you're upsizing an image. The only thing to watch is if your image is in GIF or another format that's not 24-bit color - you'll want to convert it to the RGB colorspace first in that case (not a concern with JPEG or TIFF).
I second this... This was one of the first books I read (recommended to me by someone on MacRumors) when I got into photography and it was a great read.