My mailbox is very wobbly and sags deeply to the side. I tried stuffing dirt in the base where's there's a gap, but that doesn't work. What is my best course of action?
Start by removing the mailbox from whatever it is supported by - the plastic mailbox "post" is a sleeve that's set over some actual post. It may just slip on (so you can just lift it off) or it may have a few screws you need to remove before you can lift it off. (It appears to be this model of "Step2" mailbox, and the assembly instructions do have screws into the post)
When you have removed the mailbox itself, dig the post out. If the post is rotten, or broken/cracked, you'll need a new post. If the post is OK, you'll just need to set it firmly in the ground. If you get a new post, same.
People are terribly fond of setting posts in concrete - it usually causes more problems than not, but it seems great short-term. All you really need to do is set the post vertically in the hole, add only a couple of inches of soil, tamp that soil down firmly, and repeat until the hole is full. The small amount of work involved in tamping is all you save by using concrete to set posts.
Once the post is set, slip the mailbox back on the post. If it was screwed in, replace the screws.
Although you said all you have is dirt, my recommendation is a post spike and a 4x4. Drive the spike in the ground, attach the 4x4 and put the mailbox post over the 4x4. If you ask, you may even be able to get the lumber yard to cut the 4x4 to length for you.