It's just like washing dishes - they don't need to soak for very long.
1. Fill up the sink with water and dish detergent. Alternately, you can just fill up a good sized bowl.
2. Take your cube apart - leave the core aside.
3. Dump all your cubies into the sink (or the bowl) full of soapy water.
4. Take a dishcloth or a toothbrush, and pick up each piece individually and either wipe down all sides, or give it a good scrub with the toothbrush.
5. Then rinse each piece really well and dry it.
6. Now use your dishcloth or your toothbrush to give the core a good "once-over" and wipe it dry.
7. Put your cube back together.
CAUTION: Do not drain the sink until you have taken every cubie out. Just to be safe, once you think you've got all your cubies out count them. You don't want to wash any little pieces down the drain.
Also: Depending on your lubrication method, you may want to lubricate it between steps #6 and #7. I like liquid lube, so I put my cube together and then lubricate it. If you're using a spray, it's a good idea to spray it first, let it dry, and then put your cube together.