Ok... I don't know if you're going to appreciate my advice, but I feel compelled to respond to your described experience. Let me first disclaim that these are my opinions, your mileage may vary, etc...
dreaded_beast said:
The group started off at 2nd level at the start of the campaign and has managed to work their way to 3rd following the end of last session. However, along the way, I have somewhat been "fudging" the dice, to prevent them from being killed outright or having the bad guys do a little less damage than their roll would indicate.
That's your first mistake. Never fudge the dice.
dreaded_beast said:
As the DM, I would like there to be some kind of "storyline" for the campaign, with the characters being the stars. This is my personal preference and none of the players, except one, has expressed any interest in having a "story arc". However, if one of the stars is killed, it may disrupt the flow of the story.
That's your second mistake. In my experience (15+ years of running and playing games, and many satisfied customers, so I can't be doing everything wrong...) the "story" comes out of the shared experience of the game and it is primarily an undirected confluence of player experiences. The DM can, at best, guide the flow of events, but must take great care to avoid the common trap of allowing his self-perceived sense of "story" overwhelm player freedom to influence the game.
In other words, the best games come about when the DM sets up basic situations, and allows the players to react to them, and the story is created out of the results. Personally, I have the most fun as a DM in watching the story unfold in unexpected directions, and sometimes this comes about through very unexpected means, even player character death. (Also, its a creative challenge to find new and interesting stories even in apparantly disastrous situations.)
dreaded_beast said:
In addition, I guess I don't want to feel bad if a player loses their character.
Third problem.

Get over it. Honestly, a player can always make a new character, or you and the player can find a creative way to bring the character back into play. I am always open to a creative player who suggests an interesting story pitch to save their character. They may come back as a ghost, or be reincarnated by a friendly god, or the other PCs may go on a quest to have them raised, or their spirit and memories may pass on to their heir (and new character), or... well, you get the idea.
dreaded_beast said:
Also, with the new players coming in, I don't want them to die during their first session.
This is an understandable concern, however it is never too early to learn that death is a real possibility in adventure gaming. Also, I have found that the "true gamers" will not be deterred by early setbacks. They will learn from the experiences and develop into better players. One of my high school buddies died on his very first gaming adventure from (get this) failing a climb check on a rope and falling into a 100-ft-deep pit. His next character lived for 4+ years (real time) and 16+ levels.
dreaded_beast said:
If the encounter is relatively "mundane", I don't want them to die from this mundane encounter.
You shouldn't eliminate the possibility of failure from even "mundane" encounters. Another way of looking at it is this: Why are you wasting good game time with the "mundane"? Make every encounter interesting (and exciting through the possibility of death and failure) or don't waste your time.
dreaded_beast said:
The thing that is really bad, is that I believe my players have found out, come to the conclusion, discovered, etc., that I may have been "pulling my punches" in order for them to survive. I guess part of this could be my constant nagging of "How much HP do you have left?" right before I tell them how much damage they receive.
This is the worst thing that can happen! I always tell other DMs: 1) Don't fudge your dice! and if you are going to fudge your dice, then 2) DON'T let the players find out!!
Personally, as a player, I feel somewhat cheated when playing with a DM who "pulls their punches". I would rather live or die on my own terms than survive 100 games knowing that the DM is unwilling to let me die. I am sure that some players feel differently, but it has been my experience that most players would rather know that character death is a possibility, because then they know that their success was not assured from the outset.
dreaded_beast said:
So, how do you deal, cope with, or decide when it is "appropriate" for a player to die?
It is "appropriate" when the dice say so. As a DM, I advise you to set up encounters fairly (and if you are uncertain, err on the side of caution - make your opponents a step weaker than the PCs) and roll all dice in the open and let the chips fall where they may. In this way you will increase the credibility and verisimilitude of the world and of your rulings among the players. They will see that their success is not a given, and that they may die if they are careless. This will encourage them to play more intelligently and creatively, and to pay more attention to the game (knowing that their character's lives are indeed on the line). They will appreciate their victories more fully knowing that failure is a real possibility.
I say all this from experience. My favorite recent game has had 3 or 4 total party kills in the last 3 months! (It is a pretty brutal run through the Banewarrens.) This has resulted in all of us playing smarter and more careful, and has renewed our determination to complete the adventure. After the last run, where 4 of 5 of the PCs were wiped out, the DM asked us if we wanted to take a break and try a new adventure, but we all said "no! we are determined to win!" We made new characters and altered our strategy, and the next session, we managed to take out all opponents without one character loss (although it was tough! That is a pretty nasty module!) When we finally complete this thing, we'll count the PCs that died and mark it as one of the best games we've played.
My advice is to keep it in perspective: No character lasts forever, and a player can always make a new character and keep playing. I recommend that you keep death a real possibility (if not a liklihood) and your players will appreciate it and respond with an increased enjoyment for your game.
Ozmar the Experienced, Non-Fudging "Killer" DM