An immortal in the context of a MUD is a character that is involved in the administration of the game world. They serve myriad functions, such as encouraging roleplay, dealing with cheaters and rulebreakers, coding new functions into the MUD, making new areas for the MUD, and general public relations.
Being an immortal on a MUD is a thankless job. Players spend most of their time bitching and whining about this person doing that, that person doing this back to the person who did that, asking for any of a number of little "favors" that only immortals can do for players, but aren't permitted to by the rules, and things in the same vein. There is the occasional happy moment when everyone is just bullshitting, everything is working right, and nobody's complaining, but these times are rare at best, and never happen at worst.
"Roleplay Immortals" do duties such as creating quests and things for people to do in the in-character world. These can range from large scale tournaments (think the Rose Bowl) to a simple NPC that walks into town and wants to sell some items. The purpose of these characters are to help to encourage and create roleplay within the game world. Good immortals of this sort are very hard to find.
"Administrators" are the ones that monitor players for cheating and rulebreaking, and enforce set punishments for these acts. There are a number of commands at an immortal character's disposal to help in enforcing these rules, but an outline of the commands is beyond the scope of this post.
"Coders" are the heart and soul of a MUD. They're the ones that modify the MUD code to add new features to the game. Without a Coder, a MUD is a static entity, and players soon get bored with just the base code, which is available in most other MUDs.
"Builders" are almost as important to a MUD as a Coder - the Builder creates new areas for a MUD. This can be compared to someone who creates the levels in a game such as Command and Conquer: Generals - the difference being that the maps are rendered in text, and the descriptions require imagination to visualize as opposed to spoon-feeding it to the player with graphics.
The final category of immortal is the "PR Immortal." These are the immortals with no specific jobs - most of them fit into the category of "jack-of-all-trades." They dabble in roleplay, know some building, some coding, and are at least vaguely familiar with the MUD's areas and code. This is not a hard-and-fast category - many PR imms aren't familiar with all of these areas, and most of them are immortals that merely don't do their job anymore, due to problems with the Administrators, problems with RL, or just lack of desire to do what they were hired to do. These immortals are usually the ones that talk to the players, get to know them, and tend to know more about the player's problems than the other categories, due to their lack of specialization or anything better to do.