I'm moving from London to New York. However, I don't have an apartment in New York yet so I'll be staying in budget hotels and hostels until I can find an apartment. I have around 20kg worth of excess stuff that I'd like to ship, but I don't know my address destination yet. So, is it possible to ship my stuff from London to some storage facility in New York and then I can pick it up later or have it delivered later once I'm settled in the new location? Is there such a company that does it in London and New York?
The keyword you want to search for is "bonded warehouse". I've done this elsewhere - ship to "Me, c/o Bonded warehouse, Border Town USA".
The warehouse will hold your stuff until you pick up the documentation, visit customs, and bring the clearance documents back. This probably will NOT work with the postal system - they are a bonded warehouse of sorts and things need to clear customs before continuing on.
Note that these places tend to be in the back end of airports or well-buried in the port area. You have to go there twice, and customs once (customs could be many km away). If you are not familiar with the process expect it to consume the full day and a decent amount of money. I would expect the excess-baggage fee to be cheaper.
Can you have someone in the UK mail it after you get an apartment?
I agree with Paul that what you need is a bonded warehouse, but you may also be able to contact relocating companies and have them hold your stuff for you.
The upside to doing this is that you won't have to run around the place chasing documents and getting clearances, but the downside is that you may be required to have a minimum amount of "stuff" before the company would take your business.
Most hotels will also accept your luggage for you - if you already know where you will be staying you can then ship your goods to the hotel (call ahead and let them know to expect a shipment for you). I have yet to have this request rejected, but colleagues have had experiences where the hotel refused to sign for the package unless the guest has informed them ahead of time (for security reasons) - and in one case, my friend was refused because he was not checked in yet.
I have to say 20 KG is nothing - you can save yourself a lot of hassle by just paying the excess baggage fee and then having your stuff with you when you fly. By far and away, this is the best option.