First off, the stuff that's non-user specific (i.e. install location), should be written to HKEY_LOCAL_MACHINE, not HKEY_CURRENT_USER.
However, there are a couple ways to go about what you're trying to do.
The first would be to have the product you're installing creating these keys as necessary. This is the way a lot of applications work. For example, if not available, the default toolbar layout would get created on the fly and subsequently re-used in later sessions.
If you don't go this route though, then you need to write to a couple different areas of the registry. First off, under HKEY_USERS\.DEFAULT contain all the inherted keys when new users login.
However, this won't affecting any existing users such as Administrator or David. These are stored directly off of HKEY_USERS using cryptic security IDs like "S-1-5-21-1255497644-172053269-203352104-500". You wouldn't have to locate each of these users and its underlying structure will match what you would find in HKEY_CURRENT_USER.
Keep in mind this last piece of information is how it works on NT/2000. The same basic thing exists in Win9x/Me, but I can't say for certain how much they are the same.
Hope it helps.