When you render, you set up in Render Globals the naming convention you want to use (i.e., myFile.001.tif, myFile.002.tif, etc), so you output each frame as a separate image. In Premiere, if I remember correctly, once it tries to import the first imported image, it will ask if this is an image sequence? Say, "yes" and it will import the whole thing. You should really watch the Render Globals video I mentioned above as it goes through the whole process, except uses the Free video editor, VideoMach, in place of Premiere. You might also search the forums as these questions have been asked many times before.

Not sure about maya plugins to export in other video formats. Like I said, Maya's video support is crap and no one really renders out AVIs from it (except for maybe quick Playblasts). It's not a video program. Just output the animation as images and import the sequence into Premiere. Then, output in whatever video format you want.