After Effects has movement tracking built-in. I can replace the side of a building in a shaky camera shot even if it's changing perspective. Locking the movement of added CGI to existing footage is getting very easy now.
And when you do tracking, you can redirect the output of the tracking data into the position, rotation, and size of any other layer or object.
I suggest looking at FreddieW's videos on Youtube:
http://www.youtube.com/user/freddiew
Some good ones:
His Behind-the-Scenes channel is here:
http://www.youtube.com/freddiew2
This is a guy doing this stuff out of his garage in a weekend.
The best website I've seen for learning After Effects is
VideoCopilot.net. If you watch Fringe, the opening title sequence is by that guy (Andrew Kramer) who has also done a ton of other TV effects. His basic training is what I suggest.