How full is my iPhone voicemail box?
Depending on what carrier you have you can try the following:


If you have visual voice mail you should be warned when you are at or near the limit in Phone > Voicemail
Try calling your own number. Most carriers use that to access your voicemail. If it asks for a password, it will most likely default to the last 4 digits of your phone number. Once connected it will most likely tell you if your voice mail is full. You can also delete messages from there. 
If the above option does not work, call your carrier and ask how to access your voicemail.
If all else fails you call from a different phone (house phone or friend) and test it out. You could also use a spoofing service and call your own number.