Visas are required for everyone apart from passport holders of CIS countries. A 'Letter of Invitation' LOI is no longer required by citizens of Austria, Belgium, France, Germany, Italy, Japan, Latvia, Malaysia, Spain, Switzerland and United Kingdom, but is still required for most others, e.g. for Canadian & US citizens under the simplified visa procedure.
To apply for a visa complete the application form from here, print out the resulting pdf and take to your printed form, together with some photos and a photocopy of your passport to your nearest Uzbek embassy. They will then ask the MFA in Tashkent for permission to issue a visa, which takes 7-14 days. Once this permission is granted you can pick up your visa. To avoid 2 trips to the embassy you can get an LOI in advance by email and once approval has been granted you can pick up your visa from your chosen embassy in only 1 visit - this is handy for people travelling who want to pick up a visa 'on the go'. An LOI can be obtained from travel companies when a hotel booking is made. Talk to your local travel agent in your own country. The LOI will typically cost US$30-40 for a short stay. For the latest information see the website of the Ministry of Foreign Affairs (http://mfa.uz/eng/).
Within 3 days of entrance to the country, you need to make registration, an official statement, indicating the address you are staying at. If you stay at reasonable hotels, they will do it by default, however if you stay at a house, you will face a lot of bureaucratic paperworks in order to register yourself.
When you enter Uzbekistan expect fairly lengthy immigration and passport procedures, but these are fairly painless. In particular you will be asked to declare all the money you are bringing into the country - don't worry about this - declare everything you have and make sure you have less money when you leave. The Uzbek govt don't want precious foreign currency leaving the country.
Travel permits are required for the mountain areas near the border to Tajikistan and Kyrgyzstan, including great parts of the Ugam-Chatkal National Park and Zaamin National Park.
There are only two border crossings between Kazakhstan and Uzbekistan :
Gisht Kuprik Chernyaevka between Shymkent and Tashkent is the main road crossing between Kazakhstan and Uzbekistan . A shared taxi or marschrutka from Kolos bus stop at Shymkent to the border costs about US$ 4. The trip takes about 1 hour. The border is open 7am to 9pm Tashkent time. You will have to walk over the border and to take a taxi from the border to Tashkent, which will cost about UZS 6000. There are reports of waiting times up to 5 or 6 hours at the border.
There is another crossing between Beyneu in Western Kazakhstan and Kungrad in Uzbekistan.
And another crossing that allows vehicles through at Chinaz in Uzbekistan.
Busses from Bishkek to Uzbekistan stop at Gisht Kuprik Chernyaevka border. You will have to take a taxi from the border to Tashkent for UZS 6000. A transit visum for Kazakhstan is required.
You can take a taxi or minibus from Jalal Abad to Khanabad 20som and walk over the border.
You can take a taxi 50som or minibus 5 som from Osh to Dustlyk Dostyk and a shared taxi from there to Andijan in Uzbekistan
It is about 55 km from Dushanbe to the border at Denau. Taxis depart from Zarnisar Bazaar in Dushanbe. A seat in a taxi will cost about 8TJS and the trip will take about 90 minutes. There are MinÃbusses from the border to the town of Denau. From there you will have to take a shared taxi to Samarkand.
You will have to take a shared taxi from Penjikent to the Tajik-Uzbek border 5 TJS, 22 km and another one from the border to Samarkand about 50 km.
Usable passenger services only exist to Kazakhstan and via Kazakhstan to Russia and Ukraine. These include the following trains:
Tashkent - Moscow 3 times weekly: Train 6 Uzbekistan leaves Moscow on Mon, Wed and Fri at 23:15 and arrives in Tashkent at 22:35 on Wed, Fri and Sun. The distance from Moscow to Tashkent by rail is 3,369 km.
Tashkent - Ufa 3 times weekly
Tashkent - Celjabinsk once weekly
Tashkent - Kharkov once weekly
Tashkent - Saratov every 4 days
Nukus - Tashkent - Almaty once weekly
There are also railway lines linking Uzbekistan to Turkmenistan and Tajikistan. However, service to Turkmenistan is suspended.
Note that the train cars are very old, built during the former Soviet Union. The equipment is outdated and mostly on the life support, there are no showers, the toilets are small and dirty, and there is no air conditioning. Even the undocumented Uzbek workers in Moscow typically fly home instead of taking a train. Only consider this option if you have taken the regional trains in Russia and know what you're getting into.