We need lots of details, source material, export format, GPU as a starting point
And here I thought it would be a simple thing! You would think I would learn.
Source material is an H.264 MP4, exporting to an H.264 MP4, GTX 580 for my GPU.
What version of Premiere are you running?
Are you sure that your GTX 580 is running with Mercury Playback Engine Hardware Acceleration? H.264 encoding is can be both CPU and GPU dependent especially in Premiere Pro CS5.5.2.
Are you many effects and/or are you using any third party effects?
I am only pretty sure that it is haha. Back when I built the computer I was using a 460, then for gaming purposes updated to the 580. I added it to the file for the hack, and at that point in time I did see the mercury playback setting as hardware or something along those lines. My whole timeline was yellow, which led me to believe it was working normally. When exporting though, in NVidia Inspector my GPU usage bounced between 0% and 1% so I just assumed exporting was one of the things CUDA didn't benefit me for.