I´m not a fan of picture editing in Photoshop. I prefer NLEs.
The thing you´ll definatly need is the vector/pentool:
http://www.animemusicvideos.org/guides/PenToolGuide.pdf
77.8MB PDF with example videos
Personally I suggest Sony Vegas because it´s suited for the use of the in-program pentool and editing.
After Effects goes more into the direction of effects. Editing isn´t that fast in there as it is in other programs.
The second thing that you can use as experiment are any kind of "keying effects" (bluescreen, greenscreen). If you really want perfect rotoscopes you´ll need more or less the pentool in my experience.