Instead of using the standard Links web part, add the Summary Link Web Part that comes with MOSS.

Choose Site Actions, Edit Page, click Add Web Part button, choose Summary Link Web Part, Add.

Select New Link to add a link.

Fill in the applicable information, making sure to check the box "Open link in new window".

When finished, select Exit Edit Mode.

In the future, to add links click the web part menu button, choose Modify Shared Web Part.