In and out of the nebula are moderately easy, I would think, even if the game just swapped between stars and nebula mode. The hard bit is getting from one to the other

As for 'puffs' and 'sprites', I would say all but some very old graphics cards can handle about at the minimum 2-3000 on the screen at once

Flipside
EDIT : Let's approach this from another angle, how do the programmers feel about the likelyhood of being able to implement localised nebula, either as sprites, multiplane pofs (i.e, multiple flat planes intersecting so that a cloud texture can be seen from any angle - see Unreal's flames for an idea) or fogging?