When I went to the Relic Castle after beating my game, I found a male Volcarona. My sister said the one she encountered was male as well. Is it always like this?
No there is a 50% chance for either gender.
Source mine was female :p you would need to do many more tests to assume that though.
It just so happens that you both found a male one. It has a 50/50 chance of being Male or Female.