This will be long. I've spent a lot of time thinking about my path as a programmer, and how a CS education doesn't necessarily result in a good programmer. Alright here it goes:

To give you some context for my pedigree: I taught myself computer programming in 8th grade (I'm a senior in college now). By the time I was a senior in high school, I was capable of creating a GameBoy emulator (play) from scratch (I worked with a classmate; we split the load evenly). I majored in electrical engineering, but picked up a CS minor on the side. I'm probably a better CS person than an EE, but I am mostly interested in cyberphysical systems at this point, so that worked out well.

Now for the good stuff:

- What I found most useful when I was starting out was having a goal. Just wanting to learn program without an good intrinsic motivator will just lead to some mixture of frustration and boredom. I wanted to make video games, and that was my initial motivator for wanting to learn more. As I learned more about programming and CS, my goals changed and evolved.

- My second big piece of advice is to fail early and fail often. When you start out, you won't know what projects you are capable of tackling at your skill level. You will inevitably pick projects that are not really feasible. Eventually you will get bored or frustrated with the project and move on to working on something else. Picking projects that you can finish isn't necessarily important though. What's important though is that you pick projects that motivate you. Every time you fail you will learn something new, and every project has unique challenges that will help you grow. The more a project motivates you, the more time you will spend attacking and attempting to overcome these challenges, and the more you will learn.

- My last piece of advice is to join a community. Find a good IRC channel or forum that is noob friendly, but has experienced programmers involved. The community will serve as your mentor and give you advice on how to approach problems, educate you on what tools you might use, teach you new concepts, etc. Read as much as you can.

Now as per what language, this is somewhat dictated by your goal, but I'm going to say Python. You can learn with any language, but python is a good choice. It is widely popular, so there are plenty of resources out there. It isn't the fastest language around, but when you need to speed advantage other languages can give you, you will know enough programming that changing languages won't be a problem. If you want to make a website, you will need to learn html/css/javascript as well.

If you stay as a math major, I recommend picking up Mathematica at some point. It was a life saver in my probability class last semester when I had to do some really nasty integrals that wolfram alpha chokes on.

Best of luck!