By car
Poltava has fine road connection in most directions: west E40 to Kiev, east E40 to Kharkiv, southwest E577 to Kremenchuk, north to Hadyach, northeast to Kotel'va and Russian boundary and southeast to Krasnograd, connection with E105 Moscow-Kharkiv-Simferopol road.
From Kyiv: 330km single/dual carriageway, of average quality, however seems to be intensively improving as of October 2010
From Kharkiv: 140km single/dual carriageway, of average quality. Be careful not to exceed the speed limits, as there are some hazardous parts.
From south: go along E105 road to Krasnograd, turn left to Poltava, then after ~60km of straight road you'd reach E40 and turn left to Poltava again.
From southwest Kremenchuk: 110km along E577, single carriageway, including some hazardous areas e.g. limited visibility, narrow bridges, railway level crossing.
From north, NW, NE: prefer a straight north-south road across Opishne and Dykan'ka - average quaily single carriageway. Other road NE-SW direction from Kotel'va to Poltava is in worse condition and crosses many villages.
Do not go along other minor roads indicated on the map unless you know it's fine otherwise you may experience bad road quality or get lost somewhere in rural area.
By bus
Bus connection with other cities is fine, especially along E40 road Poltava is midway between Kyiv and Kharkiv: buses usually arrive/depart every hour or a few. It will take you 5 hours to get from Kyiv or 3 hours from Kharkiv. There are a few different carriers on these routes:
Avtolux, Günsel bus service, which provide more comfortable buses, and cost a bit more from Kyiv - up to 100 hryvnas ~ 13 US$.
National and various private bus services. Some of them have less comfortable buses e.g. old Ikarus, for cheaper price. Other are more comfortable, though ticket price is somewhat 20-25% higher. Station charge included in ticket price.
You need to buy ticket at the bus station, and then better keep it with you, ticket control is possible. You would arrive at the only one inter-city bus station called Avtovokzal ÐвÑовокзал, which is connected with municipal bus/trolley routes. Note again, that between 10PM and 6AM you'd need to get a taxi.
Shuttle-bus services, which use Mercedes Sprinter or similar. Don't confuse them with "marshrutka" which is city transportation, never mind localscan call both a marshrutka. They stay in the middle in terms of passenger's comfort, however are faster 4.5 hours from Kyiv, 2.5 hours from Kharkiv. You can find these minibuses standing at railway stations or even better reserve places by phone see advertisements at bus/train station, optionally a day or a few in advance. Be sure to find your minibus in at least 10-15 minutes before departure, because your reservation may be cancelled. Then pay money directly to driver, he would write down your surname as no tickets are usually provided. As of September 2010, it costs around 85 hryvnas 10.5 US$ from Kiev.