Some confusion in here:
Premiere is for editing, that is, cutting clips, organizing them, making your video as a whole.
After Effects is for visual effects, so you take an individual clip you've cut up in Premiere, and then you apply effects to it. This can, quite literally, be anything, from some simple color correction, to generating particles, to animating a drawing.
The confusion comes from the fact that Premiere also has some effects. In fact, many overlap between the two programs. I would say as a rule of thumb, if you want to generate anything new (so stuff you can't film), remove something from your footage, or animate something, then you need to use after effects.
Some of the best tutorials for After Effects can be found at videocopilot.net. It can seem a little overwhelming, but just look for some effect you want to learn and get going. You'll start to pick it up over time.
Of course, if you need any specific help, I can help you as well. Been doing the video editing and effects for several years now. Got a few skills under my belt.