The new permanent URI SHOULD be given by the Location field in the response. Unless the request method was HEAD, the entity of the response SHOULD contain a short hypertext note with a hyperlink to the new URI(s).
Not only can you include an HTML body - you should do. (The same applies to 302 Found replies.)