It is not necessary to delete your old wireless networks first, but doing so may eliminate confusion. If you wish to do that, open System Preferences > Network, and select Wi-Fi from the left column. Click the Advanced... button, then select your old wireless networks and delete them with the "–" (minus) button. Make sure the "Remember networks this computer has joined" remains checked.
OK then Apply.
This prevents your Mac from searching for your previous network which will no longer exist.
A new Express creates an open wireless network that you must select before you can configure it. It appears in your Wi-Fi menu like this:
Select it. AirPort Utility will load and walk you through its configuration.
Edit: If you are really using OS X 10.5.1 as shown in your profile, the above screenshot is not applicable. Instead, select the network called "Apple network nnnnnn" and then launch AirPort Utility.