Depending on your PHP configuration, your server may limit the size of uploaded files. PHP sets this to 2MB by default, which can be much lower than desired. You can see what limit your server imposes by navigating to the "Upload" screen in any album and looking for the following: "Your server limits the size of uploaded files to XXMB."
So, how do you increase this limit? Here are some options:
1) First, ask your host. They may have their own way of setting these limits system-wide, so it is a good idea to check with them first.
2) If you have access to php.ini, you will need to adjust 2 different directives: upload_max_filesize and post_max_size. Here is an example (this would allow a 50 MB upload):
upload_max_filesize = 50M post_max_size = 55M
3) Some hosts may also allow you to set these limits in a .htaccess file like so:
php_value upload_max_filesize 50M php_value post_max_size 55M