Obtaining a Visa to Ukraine
Citizens of many countries can enter Ukraine without a visa with just a passport alone, for periods of up to 90 days out of 180:

***NEWS: Citizens of the following countries can now visit Ukraine without a visa for periods of up to 90 days over a 180 day period with a valid passport:
Andorra, Austria
Belgium
Canada, Cuba, Cyprus, Czech Republic
Denmark
Estonia
Finland,  France Georgia
Germany, Greece
Hungary
Iceland,  Ireland,  Italy
Japan
Kazakhstan, Korea (South),  Kyrgyzstan
Latvia, Liechtenstein, Lithuania,  Luxembourg
Malta,  Monaco,  Mongolia
Netherlands,  Norway
Poland,  Portugal Russia
San Marino,  Slovakia,  Slovenia,  Spain,  Sweden,  Switzerland
Tajikistan
Vatican City
United Kingdom,  United States,  Uzbekistan

*Note two countries that are conspicuously missing from this list:  Australia and New Zealand

Citizens of these countries can stay in Ukraine for up to 90 days within any 180 day period without a visa. For longer stays a visa will be required. For a while there was no 180 day stipulation, which meant that foreigners could simply cross the Ukrainian border every 3 months and avoid getting a visa. As of July 11, 2007 this is no longer possible (link to decree in Ukrainian), though in practice it is still possible at certain border crossings. If you intend to stay in Ukraine for more than 90 days out of any 180, you will need to get a visa.

Upon entering or exiting Ukraine, your passport is looked over or scanned to determine the number of days in the previous 180 that you have spent within Ukraine. (Note that 90 days is a little less than 3 months, and 180 a little less than 6 months.) If this number is above 90, you could be refused entry or fined. This is more likely at Kyiv Boryspil airport and less likely at some land border crossings, such as Schehyni-Medyka near Lviv, where the 90/180 rule continues to be ignored 3 years after its official adoption.

A passport valid for six months beyond the planned date of travel is required. According to Ukrainian Presidential Decree #1008 dated June 30, 2005 (with amendment dated August 18, 2005), U.S. citizens traveling to Ukraine on short-term tourist, business or private travel do not need a visa to enter Ukraine. Visas are still required of other categories of travelers including those who intend to study, reside, or work in Ukraine. Short-term travelers entering Ukraine under the auspices of this decree can stay in Ukraine up to 90 days...

However, you still must have a passport with you to enter Ukraine!

If You Still Must Get a Visa to Ukraine
You will still need to get a Ukrainian visa in the following cases:
1. You are not a citizen of one of the countries listed above
2. You are from one of those countries, but plan to be in Ukraine longer than 90 days, regardless of the purpose of your journey
3. You plan on being employed or studying in Ukraine, regardless of the length of your visit

Getting a Ukrainian visa was never too difficult to begin with, and the past five years have seen new developments that have made it easier for foreigners to arrive in Ukraine:
1. Foreigners are no longer required to go through the hassle of registering at the local OVIR (Department of Visas and Registration, also called VVIR in Ukrainian) within three days after arriving in Ukraine. Instead, they only need to register their passports if they are in the country for more than three months.
2. Invitation letters or any other supporting documents are no longer required for citizens of the United States, Canada, Japan, Switzerland, Slovakia, and Turkey, or citizens of the countries of the European Union (but an invitation letter never hurts, and at some Ukrainian consulates abroad it is even required).
3. Now, citizens of many countries do not require a visa at all for visits to Ukraine of up to three months.

Where to get a Ukrainian visa
Visa descriptions and requirements can be found at the websites of Ukrainian consulates and embassies abroad. Plan to send in your visa application no less than three weeks before you plan to visit Ukraine, though you can pay more to get it done in three or four days' time. Or find a listing of Ukrainian embassies and consulates around the world here, or, if you speak Ukrainian or Russian, call the Ukraine Ministry of Foreign Affairs information bureau at (38-044) 238-17-37, or, more specifically, the visa department at 238-15-25.

Note that you cannot get a Ukrainian visa in Ukraine, even if you have come to Ukraine without a visa as a citizen of one of the visa-free countries in the list at the top of this page. You must leave Ukraine and apply for a visa at any Ukrainian consulate abroad.

Ukraine visa application forms can be downloaded in PDF format at http://www.ukrconsul.org/visa/VISA.pdf or requested by mail.

Requrements For Foreign Citizens To Obtain Visa To Ukraine:
1. Passport must have at least six months remaining validity
2. Application form fully completed and signed
3. Passport-type photograph
4. FOR TOURIST: Copy of hotel confirmation or letter of confirmation from tour operator with signature and company stamp. If you need one, you can contact our manager by e-mail info@albion-hotel.kiev.ua
FOR BUSINESS: Letter of invitation from Company or Organization in Ukraine
FOR PRIVATE VISIT: Your friend or relative in Ukraine must obtain an official invitation from the local OVIR (Office of Visas and Registration), and this certificate must be included with your visa application.

Visas can be extended in Ukraine within 4-5 business days at the city OVIR (office of visas and registrations) — not the neighborhood OVIR. Apply for an extension no sooner than 4-5 days before your visa expires. You cannot change the category of visa and are not allowed multiple entries back into the country during the period your visa has been extended for. In other words, if you have a multi-entry visa and extend it in Ukraine, you will only be allowed one more exit from Ukraine. As soon as you leave the country, the visa becomes void.

Remember, you cannot get a new visa while in Ukraine — you can only extend your existing visa. You must leave Ukraine to get a new visa — at any Ukrainian consulate in any foreign country.

Hence, if you plan to make multiple trips out of the country during the period you want to extend your visa for, it would make more sense to receive a new visa during your next trip abroad or even make a special trip to get the visa (to Krakow or Budapest, for example) rather than extend your current visa.