This isn't a small job by the sounds of it!
Essentially your tables will be as follows:
When users login during the checkout process you store the unique ID for that user in a Session Variable, and when you write the order to the database you store that ID in a foreign key field. Therefore the orders relate to a user.
To update the status, simply have a field in the orders table called, for example, order status. You can then change this either via free text or a drop down in the admin area of your site and that will simply change the status of the order.
Hope this helps.