The electrical signal from the cartridge is unamplified, is high impedance, that impedance changes considerably with frequency, and the signal itself is equalized on the record. The role of the preamp is to properly buffer and amplify the signal to acceptable levels, and to apply RIAA equalization.
Overview of RIAA equalization
Most of the amplitude of a recorded signal comes from its low frequencies. This causes problems for vinyl, because these high amplitudes, if directly transcribed to fit the constraints of the system, would reduce the signal-to-noise ration unacceptably at many frequencies. To avoid this, the transcribed audio is equalized so that low frequencies are attenuated and high frequencies are boosted. On playback, this process is reversed, so that low frequencies are boosted and high frequencies are attenuated. This has the additional benefit of reducing the high frequency noise caused by ticks and pops during playback. However, it has the risk of increasing rumble. The particular equalization curve used is known as the RIAA curve (standardized in the 1950s).
Preamps, like all amplifiers, are entirely electronic devices with no moving parts. Their objective parameters can be described using the usual metrics, including frequency response, deviation from the ideal RIAA curve, PSRR, THD+N, IMD, etc.
Additionally, the choice of cartridge determines which preamp to get. MC carts operate at a much lower signal level than MM and thus require more amplification and a different load impedance.
Frequency response is measured as deviations from the ideal RIAA curve. +-1dB is common for entry-level preamps, and given the other inaccuracies in LP playback, is going to be fine for most users.
Preamps must amplify a signal by 40-60dB (roughly, from 1mV to 1V) and also apply an equalization. This is a surprisingly difficult task, and some bad apples are out there. Preamps, like many audiophile components, still use a multitude of different technologies to implement these goals.
Power supplies can be an issue, especially with discrete/triode units. This usually owes more to the cheapness of the preamp, or the incompetence of the power supply design, than any intrinsic reason why power supplies or power cables or power conditioning are important.
Found most often on inexpensive preamps and preamps integrated with receivers and turntables. Even today, the requirements of preamp design often exeed the capabilities of many op amps, and expensive ICs (or complicated topologies) are often required. Op amp designs are no less complex than discrete designs.
One very great advantage of op amp designs are their generally high power supply rejection.
Discrete solid state
Found on many/most preamps. Extremely sensitive to power supply issues.
Tube preamps are still extremely popular among audiophiles, for any number of subjective listening reasons. There are actually a couple good objective reasons for building preamps with tubes, as it is thought that their electrical properties are somewhat more compatible with the requirements of preamp design. Like discrete preamps, tube preamps are very sensitive to power supply issues, but require far higher voltages than discrete preamps to operate, making power design that much harder.
Prices and Availability
Many entry-level turntables have integrated preamps. Their efficacy is unknown and usually prejudged poorly.
While audio receivers today generally do not include integrated phono preamps, receivers from the 1950s to the early 90s generally include one. Some of them are held in very high esteem. Old receivers can be obtained on eBay for $20-$100 and should definitely be studied if you are interested in that price range.
Given that preamps have existed for 50 years and using much worse components than are used today, finding a preamp that properly satisfies the objective requirements should not be expensive or hard. Sadly, preamps are such an esoteric field that you are likely to spend over $200 to find a good one. Check online stores and hifi stores, but don't hesitate to buy used.