I only know of one method, but here it is. You create a sphere the diameter of the VdW radius of water, and then 'roll' it along the surface. I know this as a Richards-Lee surface, wikipedia has another name for it.
This looks complicated, but its not. you move the probe sphere along the surface of the molecule in the XY plane until it just touches the vdW radius of the protein, keeping the center of the sphere as the surface, all the way around the molecule. If you like, you can color the surface by the charge of the position too, which is useful for discussing solvent interactions.
Then you translate along the z axis and do another contour until you run out of protein. Apparently jmol and other packages will do this for you.
Wikipedia references a more mathematical method LCPO, which I am not so familiar with.
Is this accurate? As usual with such calculations its more of a guess than an answer. You can do the calculation on any structure or any ensemble of structures (like NMR gives). It doesn't understand how the molecule might be flexible or dynamic. If you read up on your physical chemistry you see that proteins breathe and can allow diffusion into the core rather readily. If I recall right, you can get rather large molecules quenching heme flouresence in hemoglobin at room temperature.
If you are looking to dock 2 proteins, SAS might be more useful. Its an important piece of information, but not an ultimate answer. I'm afraid with proteins that doesn't happen so easily.
@bobthejoe asked about SAS for which no structure exists.
This is an extremely difficult thing to even guess at. The non helpful answer is that the surface of the protein goes as the cube root of the molecular weight of the protein.
By getting a solution of the protein and shooting it in a syhcrotron, you can get a mean radius of gyration pretty easily which will give you an ellipsoidal volume (and surface area) for a protein. Again most of the particulars would be lost and this could easily be off by 25% for an irregularly shaped protein. For a regular globular protein it might give an answer similar to the power law above.
I have seen physical chemistry experiments that look for changes in osmotic pressure when the salt concentration in a solution of the protein changes substantially (Adrian Parsegian's work at NIH in the late 80s).
I doubt you will find any of these answers useful as their mean error is going to be very large (20-200%) and also assumes the protein is soluable and amenable to the experimental conditions.
Solvent probes can help too. For instance exposing the protein to D20 then doing mass spectroscopy on the protein. This is still only going to give you a general idea of how much of the peptide is surface exposed. Protein structure is still pretty necessary to getting any accurate measurement of SAS I think.