That varies depending on many factors such as the resolution that you shot with, as well as what resolution you want to upload with. Also a factor is how fast your Internet connection is, and whether using some of the higher resolution and better quality options will be too time consuming for you due to the large file size. These are all factors that you will have to judge, and decide for yourself which best suits your individual needs.
Assuming that you are shooting HD video, using the current version of Premiere, and want to make your video view-able in HD, generally choosing H.264 as the format and then either YouTube HD or Vimeo HD for the preset will work out very well. Both of those options will upload in 1280x720, and give good quality for typical Internet viewing. File size can be a little large, but is usually manageable. If you have a slow Internet connection and need to reduce the file size further, then you could instead use either the Vimeo or YouTube SD preset options. Just realize that you will be giving up significant image quality if you originally shot in HD.
Now if you did shoot full HD and want to upload in 1920x1080, exporting to H.264 can result in a rather large file. In fact, if you use one of the HDTV 1080 presets, using H.264 will result in a file about 70% larger than if you were to instead use the MPG2 format option. So if you wish to upload in full 1080, then I recommend using MPEG2 as the export format if file size is a major consideration for you. On the other hand, if image quality is your dominating concern, then use H.264 as the format. You can experiment using both yourself, and see if you think that the larger file size created with the H.264 option is worth it to you when uploading 1080.