This question deals explicitly in how the mechanics of Pathfinder functions and not in how I should resolve this at the table; in Pathfinder, if a character is immune to an effect and then targeted by an ability that both permits a save and afflicts that effect, do they still roll a saving throw? For example, if a character immune to Paralysis is targeted by Hold Person, or if a red dragon is targeted by a fireball, are saving throws still 'supposed' to be rolled?
No Order of Operations Exists...
These are rules you'll have write. It's unfortunate in d20 that there's no quantified step-by-step order for combat and applying effects a la most trading card games. Were there, we could just say, "Immunity applies during step X, Damage Resolution, after Saving Throws but before Inflicting Effects," or whatever.
...But If You Want My Opinion
Yes, if only so the creature can choose to give up that saving throw.
Immunity shouldn't remove options everyone already has that aren't part of being immune. As everyone has the option of giving up a saving throw before knowing an effect's effect, immunity shouldn't change that.
Therefore when a creature is subject to an effect that requires a saving throw, the creature can choose to either make the saving throw or voluntarily give up (i.e. fail) that saving throw. Then the DM determines if the creature's immune to the effect.
Thus, unless the creature already knows an effect won't affect it (via a successful Spellcraft check, a successful Knowledge check that's revealed the opposition's abilities, or prior experience), the creature attempts the saving throw despite realizing an instant later that it possesses immunity to the effect.
That's because Pathfinder (and its antecedents) is a dangerous place, and what individuals can do varies wildly. A creature is safer if it always attempts saving throws versus affects, even if it thinks it might be immune to such effects because there's usually a random component to identifying effects, and being dumb gets it killed. Even a red dragon--who's immune to fire--will still make a saving throw versus the spell fireball [evoc] (Pathfinder Role-playing Game Core Rules 283) because there's no way to anticipate how a particular caster's fireball is going to differ from any other caster's fireball.
If immunity is checked first there's no opportunity to voluntarily give up the saving throw, and that opportunity should exist even if the creature's immune if for no other reason than to let the DM, when describing the spell's effect, tell the players that the creature appears to give up its saving throw, acting all awesome because the creature suspects he's immune.
If a Precedent's Absolutely Necessary
When spells are printed, they're printed with a Saving Throw first and the Spell Resistance after, so absent another order, those are checked in that order. Linking spell resistance to spell immunity is easy, but making the jump from spell immunity to immunity is harder, but, hey, the words are there.
There is no precedent in the rules for it to matter, so I doubt any rule addresses it. You are using a new mechanic, so create rules for it. Even if there is some RAW that defines the general case, people probably don't know it, since this is super obscure. So just give a specific rule in the effect for what you want to happen in this case, and also in the case of waived saving throws, e.g. for (harmless) spells. Don't rely on obscure RAW here, that will lead to very different results for different tables, even before anyone intentionally houserules anything.
There's nothing saying you can't, but it's not likely to make a difference.
It's analogous to “(harmless)”, in my opinion.
As an addendum to other answers, I would like to offer some help on the issues you mentioned in the comments. There is at least a couple precedents for what you are trying to do. The Starsoul bloodline's arcana reads:
If a Starsoul sorcerer throws a Fireball at a Red Dragon, does the dragon have to roll to avoid being dazzled? Jinxed spell is another example.
As it turns out, we can find an answer under the entry for Immunity (emphasis mine):
Despite not being the clearest formulation ever, this seems to show that a creature does not suffer from secondary effects triggered by an effect it is immune to, no matter if it succeeds on its save or not.
Back to our example, a Red Dragon receiving a Fireball from a Starsoul sorcerer would not be Dazzled. In fact, the Red Dragon cannot be affected by any secondary effect triggered by a Fireball or any other fire effect.
So the answer is "no," no one in reality bothers to roll saves to things they are immune to and the rules are silent on the subject. If you are writing some mechanic that expects them to even recognize its lack in gameplay, it needs to be super explicit and will suffer from the fact that it relies on an operation that flies in the face of common use, whether a tortured reading of RAW justifies it or not.
At my tables, I have never rolled a saving throw for a creature with permanent immunity to an effect against that effect, regardless of source or other abilities. Creatures who were born immune to fire do not dive for cover when fireball'd. If I had a player request the save, though, I would probably allow it.
Rules as written
(from the PFSRD)
Fireball explicitly requires a saving throw for every target in the area of effect. (Players may choose to fail the save, but not choose to succeed.) Immunity does not mention saving throws at all.
If effect A says "This character must do this" and effect B doesn't contradict it, then it seems safe to say that the action is still required. The "any secondary effects" line gives me pause... but this seems to be a corner case similiar to Burst weapons vs. critical hit immunity... the "any secondary effects" line doesn't prevent a Burst weapon from doing its Burst damage on a confirmed would-have-been-a-critical-hit against a critical-immune creature, so an ability that isn't a part of the fireball (say, a feat on the immune target that says "when you are in the area of an area spell") should still trigger.
(PF FAQ, in case you wanted the exact wording on the Burst vs. crit-immune case)
The rules don't say you DON'T save, and unrelated effects can still occur. If a separate ability (NOT the ability the creature is immune to itself!) should trigger off that saving throw, go ahead and make that save. At a table that isn't strictly bound to RAW, though, I would give an immune creature the option to auto-pass the save, the way virtually all spell targets can choose to auto-fail a save.