All this data is potentially out of date, and should be taken with a truckload of salt
A nerf is a change in the game's mechanics, especially related to the way a particular ship or module performs, which decreases the strength of that module or ship.
Every ship in Eve has a set of bonuses which sets it apart from other ships in its class. A Vexor cruiser, for example, has a 10% increase to drone hitpoints and a 10% increase to mining yield per Cruiser skill level. This makes the Vexor a very solid drone and mining ship. These bonuses allow for diversity in the Eve universe as players who wish to maximize a certain aspect of their ship, whether it be sensor strength, turret/launcher strength, tank strength, or drone strength, may decide to pick a particular ship that maximizes their advantage.
When a bonus becomes too powerful, however, a loss of balance in the game exists. For example, if the Vexor cruiser had a 100% bonus to drone hitpoints per skill level, then a player could have a 5 medium drones that can destroy any other cruiser or battleship for that matter with little effort, and that bonus does not take in account any other bonuses that player might have to drones that would make it even more destructive.
If this were the case, then CCP's (and likely CSM's) reaction would be to "nerf" the Vexor, and reduce the bonus to a more reasonable level.
How ships are determined to be "too strong"
There are many "warning signs" that a ship would need to be nerfed. In the example above, such warning signs may include the vast majority of cruisers in the eve universe being Vexors, a Vexor's price fluctuating wildly, or simply observing a combat battle that comes lopsided in one's favor as soon as a Vexor arrives.
Other warning signs that a change in a game's mechanics are necessary is if there is an entire class of combat ship that is greaty missing in the battlefield. A single ship or module's strength may make an assault ship, for example, "useless" or at the very best "way over-priced" to be of any use.
It should be emphasized that a nerf is usually only implemented when a ship has a very obvious advantage over another ship it is not intended to have. A cruiser that is designed for combat against a battleship is not "bad" in and of itself, as long as that advantage creates a disadvantage in another aspect (such as against other cruisers or against frigates, or perhaps against a particular battleship fitting).
Also, ships which are powerful over other ships should be so due to the cost and/or skills put into it. A cruiser which costs a mere $5,000,000 with a $2,000,000 fitting easily taking over a tier III battleship with expensive Tech II fittings will usually prompt a "nerf." A cruiser that is fitted well that provides a good challenge over a battleship or even a carrier isn't necessarily bad, as long as the expense of the fittings or any other peripherals justify that strength.
Players' opinions of nerfing
Players have differing opinions on the effects of nerfs, some saying it is unfair to have a player spend a lot of time saving up for and training weeks of skillpoints to fly a particular ship (which might include training many faction-specific skills if the ship is outside of that player's birth-faction), only to have it nerfed soon after. Others argue that nerfing takes out some of the more interesting aspects of combat (Most can tell that when a dreadnaught, carrier, or titan comes onto the battlefield, things are going to get interesting, but when a ship that is known to be super-powerful under certain fittings comes on, players won't always know that ship's true capabilities without a decent ship scanner).
Other players do not disagree with nerfing in general, but might disagree with a particular nerf due to their effects on their particular line of work. For example, nerfs that reduce the strength of a particular pirating strategy often irk those who are making a living of piracy, while a nerf that reduces the strength of a ship that's known for its missioning strength might frustrate those who mission for a living. Nerfs which affect a certain style of play (such as solo-PvP, ganking, or hi-sec PvP) often result in players accusing CCP of "favoring" one type of player over another. No matter what the reason for the nerf, all changes to a game's mechanics will always result in controversy and intense discussion.
Examples of nerfs
The "nano-nerf" was one of the most well-known nerfs, as it addressed a long well-known advantage a ship with many low-power slots and at least one medium-power slot had over virtually any other ship. (Read more here: http://www.eveonline.com/devblog.asp?a=blog&bid=574)
The "Nos-nerf" addressed many complaints about the use of nosferatus. Nosferatus until the end of 2008, where able to drain the opposing ship's capacitor until it was gone, the giga-watts transfered to the offending ship. Furthermore, a ship could have as many nosferatus as they wanted, which made the Dominix especially deadly because of its capabilities as a drone ship, which essentially allowed the 6 high-power slots to become a capacitor draining monster of a ship.
As a result, CCP introduced the "nos-nerf," which essentially meant a nosferatu could only "match" what the offending ship's cap had, percentage wise. (If the victim had 50% cap, and the offending ship had 20%, then the victim can only go down until the offending ship's cap matches the offending ship).