Overwrite add/edit form
As far as I know, path templates are built-in Drupal 7, so just do this:

page--node--add--blog.tpl.php (for blog)
page--node--add--story.tpl.php (for story)
etc.
etc.

Clear cache!