If you consider that all replies to a message are also messages I would give an id to every one of them and use these URIs:
#message {id} (only the message, no replies)
/messages/{id}
#replies to the {id} message (a list of the id's of the replies)
/messages/{id}/replies
To create a new message do a post to the uri
/messages
To create a reply to a message {id} do a post to
/messages/{id}/replies
Update
I will modify here my previous answer. Hopefully this time in a correct Restful style.
You have an entry point uri, let's call it {messages}.
GET {messages} -> list of uris of all the messages, {message1}, {message2}, etc.
GET {message1} -> responds with the message1 document, for example in xml it could be:
<message responses="{link to message1 responses}">
<date>...</date>
<body>...</body>
</message>
{link to message1 responses} is the link that the client has to follow to get the list of uris of the responses.
If a message is a response to another it will include that in his content, for example
<message responses="{link to message1 responses}" inResponseTo="{uri}" >
<date>...</date>
<body>...</body>
</message>
Now to add new messages just post it to the original {messages} uri. If the message is a response to other message just include it in its content (note that this is an efective change to the inital answer where you post the replies to an special uri).
To modify some message do a PUT to its uri.
All the uris coudl follow thats of the first part of the answer, but this is not necessary.