1. USPS. ie, The post office.
2. Depends on the fish, but with hardy shrimp, livebearers, and snails, priority is usually fine.
3. Overnight is usually a minimum of $45, and sometimes as much as $70-$80. Priority, you can use the 'prepaid' boxes that use a flat rate- Most packages will be $11, and only the very largest shipments will me &$14.50. Snails and some plants can easily fit in the $5.50 box
I don't use oxygen, but I do use 'Kordon Breather Bags', which allow O2 exchange through the plastic. I also use 'Bag Buddies'- A small tablet that you add to the water. It adds Oxygen and a fish tranquilizer to keep the fish calm.
Which service is the cheapest? USPS Priority is by far the cheapest, but as far as overnight services go, I don't know.