Tested in WP 2.8.4
Edit the following file within your wordpress installation.
wp-admin/edit-link-form.ph
Find this line and add the code below to add the nofollow relationship (rel=”nofollow”)
<th scope=”row”> <?php /* translators: xfn: http://gmpg.org/xfn/ */ _e(‘identity’) ?> </th>
insert the html code below
<tr>
<th scope=”row”> <?php _e(‘seo’) ?> </th>
<td><fieldset><legend> <?php _e(‘seo’) ?> </legend>
<label for=”external”>
<input type=”checkbox” name=”seo” value=”external” id=”external” <?php xfn_check(‘seo’, ‘external’); ?> />
<?php _e(‘external’) ?></label>
<label for=”nofollow”>
<input type=”checkbox” name=”seo” value=”nofollow” id=”nofollow” <?php xfn_check(‘seo’, ‘nofollow’); ?> />
<?php _e(‘nofollow’) ?></label>
</fieldset></td>
</tr>