It seems funny to an English speaker that even if the person you are talking to is a man, you still say "Sua mesa".....
Yes, it takes getting used to that the possessive takes the gender from the noun it modifies. Many languages are like that.
Here is a table of the Portuguese possessives which might help:
I was wondering why this can't be "Their table" instead of "Your table". Does anyone else know?
It can be both, but more commonly used for "your table". Judge it based on context mostly I'd say. For her/his/their table you can also use "mesa dela/dele/delas/deles".