First pick a technology that will be provide the foundation of the message board (i.e. XML or database).
I prefer database storage because it's faster and easier to work with. Storing messages in XML is more portable, but more burdensome on the server.
Basically the way I think of forums is a hierarchy of
Forums -> Messages -> Replies
So the way I attacked this problem is:
1) create a table of forums
2) create a table of messages with a foreign key to a forum
3) (optional) create a table of replies with a foreigh key to the messages
Number 3 is optional because you can alternatively have a column called 'parent_id' or somthing that is null when it's a parent and a id of another message if it is a reply.
There's also the issue of hierarchy in replies (i.e. reply to a reply to a reply), in which case a recursive algorithm is often implemented. I prefer all the replies having one parent message instead since it's easier to implement.
For simplicity's sake, I'd recommend the style of this discussion board.
My working forum is on http://www.sdlambdas.com