Even though Mykolayiv has a major Ukrainian commercial sea port (http://www.portnikolaev.com/) 5 mln.t in 2004, there are no regular passenger lines.
There is an airport at Mykolayiv Nikolaev IATA: NLV (http://www.airport.nikola...). Daily flights to Moscow-Vnukovo, operated by UTAir Aviation, a regional Russian airline.There are also 3 weekly flights to Kyiv, Ukraine and 2 weekly flights to Istanbul, Turkey.
The nearest major airport is Odessa. There are daily flights from/to Odessa operated by "Ukraine International Airlines", Aerosvit, Austrian Airlines, Polish Airline "LOT", Czech Airline "CSA", Hungarian Airline "Malev"
Direct trains to Moscow 26 hours, Kiev 10, Lviv 18, Odesa 5, the Crimea 8 hours depart every day. Train departures timetable (http://poezda.org.ua/city...). All trains have coach cars.
Main routes to Kherson 65 km, Odesa 120, Uman' 320, Chishinau 325, the Crimea 350, Kiev 500, Kharkiv 520, Lviv 950. Usually gas is cheaper than in W.Europe, approximately the same price as in N.America. Check if you can hire a driver with a car. Be careful if you travel alone and don't forget to carry a mobile phone. Hitchhiking is not recommended. The roads are terrible and dangerous. Use seat belts despite of comments from local drivers.