You can drive a small bipolar stepper motor using an L293, SN754410, or L298
If you find a unipolar stepper motor (not uncommon in the paper advance on cheap printers) you can drive that relatively easily with discrete NPN transistor switches. In theory you can do a bipolar motor that way, but the circuit is a bit trickier (it's easy to get both the high and low transistors on and as a result short out the power supply, making them rather warm). Besides printers (copiers?) floppy drives are another salvage source, but hard drives switched to voice coils ages ago. Lots of surplus outfits will sell you motors; if you aren't looking for something powerful enough to run a machine tool you probably won't have to spend much.
Since you are very new to embedded programming as well, you might want to look at one of the "motor shield" type solutions - not necessarily to buy (though of course that is an option) but to study the plans and example software.
If working with a salvaged motor for which you don't have data, start with low voltage/current until you get movement. One thing that can be interesting to do is to take a <1 amp power supply and work out the series of voltage applications to the winding by hand connnecting them to slowly step the rotor. You can buy chips such as the L297 which generate this sequence to control the power driver chip, or you can do it yourself in software.
Actually making a motor may be fairly tricky, but people do make brushlesss motors which are stepper's lower-pole-count cousins. For early experiments ball bearings are likely not your greatest concern - plastic or oil-impregnated bronze sleeves might serve. But rollerblade wheel bearings are fairly cheap: mounting them is going to be a big part of the challenge (and a challenge which starts to stray from the topic of EE stackexchange)
Yes, it's almost certainly a good move to learn to use C as well as possible (C++ will give you a helpful starting point, although as leftaroundabout notes, there will still be plenty to pick up, especially the differences between coding for small embedded systems compared to writing for something like Windows) given it's ubiquity.
Most microcontrollers below a certain size (e.g. PIC, AVR, MSP430, etc) use C (or assembler) as there are many high quality (free and $$ versions - e.g. many commercial compilers are based upon the free GCC compiler) C compilers available.
You do get other languages like the excellent JAL for PIC (original author Wouter Van Ooijen who is a member here), PICBASIC, Ada variants, but due to it's popularity and number of compilers available, I'd say C is the language of choice for most. While this certainly doesn't mean it's the best language, using the most popular language comes with obvious advantages (documentation, support, portability, collaboration, etc)
For the more complex and larger 32-bit micros like many ARM variants, there are also C++ and other compilers available.
I would jump right in and grab a few development boards and get coding. You could pick a low end 8-bit micro like the PIC16F (many starter kits on Microchip Direct)
A middle of the range 16-bit micro like the PIC24, and also a C/C++/embedded linux ARM of some sort - the STM32F4 ARM Cortex M4 Discovery is an very cheap dev board that might be worth grabbing.
On the programmable logic and hardware description language (HDL - the big two are Verilog and VHDL) side, it may be also worth getting hold of an FPGA or CPLD dev board from Diglent or similar.
If you don't want to wait for a dev board, you could download MPLAB or MPLABX and use the excellent simulator to try your hand at PIC development. Same goes for other tools too, for instance you can download Xilinx ISE Webpack for free and try out HDLs and programmable logic design.
Best Answer
For digital logic, focus on hardware description languages hdl, such as verilog or vhdl.
For analog simulation, you'll want to be familiar with spice.