What are you afraid of? Relace it all at once. There's plenty of information on the net to tell you how to create the spoke pattern. If you get hopelessly frustrated with truing, you can always take the wheel to your LBS and let them finish it up for you.
That's the best experience you can get.