How do I solder a surface mount (smd) voltage regulator?
No need for solder paste. 

I use an RMA rosin flux pen (it works like a Sharpie) to coat the pads (especially the big one) with flux and then solder. Liquid flux with a brush works well too.  Heat the big pad and tab from the side and introduce enough solder to get it thoroughly attached. If the board is reasonably fresh it will suck the solder in under the large pad quite readily. Liquid flux and flux pens are a bit of a pain because they can't be shipped by air, so they're easiest to buy locally. Liquid flux in large quantities even attracts a Hazmat shipping surcharge. 



Make sure the part is quite flat before soldering with essentially no gap before introducing the solder.

If the part does not need to dissipate much power (for example, a regulator where you don't expect more than a few hundred mW) you can just tack the end of the tab rather than flowing the solder right under. Make sure the connection is solid- especially on the DPAK package (the one you show is a D2PAK) because a lost ground on a 3-terminal regulator can have unfortunate consequences. 

If, for some reason, you have to remove the part and replace it, clean the pads thoroughly by sucking up the solder (for example, with fresh solder wick) and make sure the new part sits dead flat on the cleaned board before attempting to solder it on.