Yeah, I agree that Mix Master Mike probably had custom vinyl made up with each of the tracks he wanted to mix with. For years (maybe decades!) you've been able to buy scratch records too... 12"s with all the different classic sounds people like to scratch with, including a test tone.
The super duper basics of mixing are as simple as this:
Put the record you want to play first on turntable 1 and start playing it. Have the crossfader on the mixer over to one side so you can only hear turntable 1.
Put the next record on turntable 2. Listen to the record through one of your headphones to find the right track. Put your hand on the vinyl to stop the thing from playing.
When the right moment comes, take your hand off the vinyl and move the crossfader to the middle, so both tracks are playing coming out the speakers, and then keep moving the crossfader across until you only hear turntable 2.
Put a new record on turntable 1 and repeat this process until you're bored.

If you want to beat mix, i.e. get two records playing in time with each other, you cue up your second record in your headphones and then move the pitch slider on the turntable to speed up or slow down the track until it's in time with the first one. Using your hand on the turntable, manually wind the record back to the start of the first beat of the track, and then let go at the right time so that the first beat lands at the same time as the first beat of the bar on the other record. Listen for a bit in the headphones to see if it's falling out of time. Make subtle adjustments to the pitch, or if it's pretty damn close use one or two fingers on the vinyl to either push it a bit forward (to speed it up) or pull it towards you (to slow it down). You'll sometimes see DJs softly tapping the vinyl to slow it down ever so slightly if it's playing a bit too fast.
When everything's awesomely in time you can either just crossfade between tracks or wind the 2nd record back to the start of the track and then do a cold cut (i.e. push the crossfader fully from one side to the other as quickly as possible).
Bear in mind that if you're changing the speed of the record you're doing it by changing the pitch. Depending on the kind of music this is more or less of an issue, but with pop and rock and stuff this could be horrific. The chance of finding records that will play in time with really similar tunings is pretty ... slim. That's why dance tracks are often written with intros and outros that are mainly just beats, so you don't have to think too much about clashing tones.
DJs often do a "baby scratch" (where you just push the record back and forth and make that 80s "doowa doowa" noise) when they want to get the first beat of a phrase lined up - not sure why, but physically it's easier than just holding the record still and then letting it go and hoping it'll land on the right beat.
-
If you do go the vinyl+digital route, I'd strongly recommend Serato's Scratch Live product. Serato has an excellent rep for support compared to whoever does Final Scratch. Dunno about the smaller competitors.
Any more questions, I'll do my best to answer.