There's a couple of options here.
1) You can use pathauto module to rename the paths. These paths then become perfectly useable at the server level, but the old node/add and node/%/edit paths would still exist.
2) You can make a custom module which implements the paths via hook_menu, copying the appropriate code out of node.module's hook_menu implementation. This also would leave the old node/add and node/%/edit paths on the site, but you could then use hook_menu_alter to unset the appropriate paths from the menu array.
3) You can use the custom_url_rewrite_inbound and custom_url_rewrite_outbound functions as Olav suggested.
Honestly, the first option is generally the better one, as it will be faster and not open up unexpected bugs. Method 2 will definitely change what you want, but will also involve changing some fairly basic paths that Drupal depends on, and it's possible that this will mean quite a lot of debugging sessions as you discover corners of the node module that weren't covered in your changes. Method 3 I'm not as familiar with, but it looks like it allows you to rewrite paths as in 1, but make them more real, but there's possible problems with performance lurking there, and again, a good amount of debugging to do.