Start by taking any programming language and working through some of the problems at Project Euler. Then come up with an idea for a project you want to build, and build it, one piece at a time. It might be a website, a calculator, a command line app, a GUI app; doesn't matter.
Why C? It's not a bad choice, absolutely in my top five, and the #1 best choice for quite a few things. I'd say the other most popular general purpose languages are - in no specific order - C#, Java, Python, and C, with a second tier being C++ and Perl. PHP would make the list, but it's specifically tuned to web applications; it's not as general purpose as the rest.
edit:
The first course in a computer science degree program is usually "how to program". You'll work through an introductory book, maybe Deitel and Deitel (those are the authors of one of them).
In the second course, you'll learn data structures; how to efficiently store and work with data. Data structures would include linked lists, stacks, queues, trees, heaps, and hashtables.
As a general word of advice, if you're learning C, I'd probably pick up the book The C Programming Language by Kernighan and Richie. It's not designed to be a first programming book, so don't let it intimidate you! I mention it because I'd bet that every C programmer eventually owns a copy.
edit
For math, the useful things are often probability (permutations and combinations), logic (up through Demorgan's law), and inductive proofs (recursion!). The current book I've seen on the more theoretical half of this is Introduction to Mathematical Thinking, by Gilbert and Vanstone, while the book I learned on is fifteen years old and $5, Classical Algebra, also by the same authors.
For logic and probability, just look at Wikipedia for awhile, and go further if it interests you.
edit
Mark Weiss wrote a Data Structures book in Java, and another in C++; both were decent introductions to various ways of working with data. There are a lot of good data structures books.
The last book I'd recommend for learning to program is "Introduction to Algorithms", by Cormen, Leiserson, Rivest and Stein. This is a really large book, relatively heavy on math and theory, that covers the core of all modern algorithms today. It explains data structures as well, but much more from a theory angle instead of directly from practical code. It's awesome, but definitely not the first book you'd want to work through. I've also found that reading this book is much easier if I can go back to Wikipedia to get more examples of the same thing.
Lastly, the book I recommend for learning how to work on a software development team is The Pragmatic Programmer. Very little programming - lots of software development advice.