How do I get started in theoretical CS ?
Let me provide an answer from the other side. I've had a few undergraduate student researchers work with me. The experience has been mixed: with some, I have published papers and have work in progress, and with others, we never really got off to any kind of start. 

It's great that you know what you want to do. As an undergraduate, here's what you should be focusing on:


Building the mathematical "muscles" that will help you when you start working on problems in earnest
Exploring different aspects of theoretical CS to get a sense of the area and figure out what kinds of problems/areas you find interesting
(depending on the area) working out some puzzles, maybe solving some exercises, and working your way up to a research question.


Find a professor to guide you, and PUT IN THE TIME ! The hardest thing you'll face is creating the open time to think about problems in the midst of classwork, assignments and exams. But you need to reserve blocks of time for your independent study and research otherwise it will be very hard to make any kind of progress. How you do this is upto you: maybe you can find a professor to meet with you once a week and set intermediate goals for you, or maybe you can set a long term goal (working through X exercises from a text) and work steadily on that.