As SciAm's Ferris Jabr explains in the video up top, the short answer is: nociceptors. Many animals have these sensory neurons. Some animals have weird ones. Take naked mole rats, for example — NMRs have mutated sodium channels that limit physiologically "normal" nociceptor firing, thereby blunting sensations of pain.
Similarly, humans with mutations in Nav1.7 (another important nociceptor sodium channel) have been known to feel no pain whatsoever.
As for the lobsters, David Foster Wallace would have you know that even these big sea-bugs have nociceptors, and you should maybe bear that in mind the next time you drop one in a pot of boiling water.