2016 update: all three major national operators offer similar plans. Kyivstar, Lifecell (formerly Life), Vodafone (formerly MTS, UMC) offer 3G voice and data connectivity at just a couple of bucks per month. There are other 3G operators, however a traveler would normally prefer one of the three mentioned. SIM cards are everywhere and available freely.
From the mentioned above three, Kyivstar and Vodafone are believed to be slightly "bigger" and offering better coverage outside of populated areas. Lifecell in turn is known as more addressing youth and believed to offer better mobile internet connectivity in densely populated areas. However I suppose all three are close in quality of service. All three tend to offer cheaper or free calls on home network. It is common that the number remains valid for a year, which might be interesting to those expecting recurring visits to Ukraine in future.
Perhaps something new from the operators in 2016 is their low-cost offers for international calls. The operators offer attractive calls abroad and in roaming for specific directions. For example, Kyivstar's offer for international calls to selected countries is cheaper than Skype-Out calls, with decent voice service quality. Base services are presumably so cheap that they cannot go any lower (imagine $0.2/mo for unlimited voice calls on home network, 5 GB of 3G mobile internet at $1.2/mo?), so they started attracting users with auxiliary services.