If I need to keep some config separated out from code then what should be the best approach? I have some Web Services that needs to be invoked from Apex class. Web Services URL vary based from where it was invoked i.e if Apex code is deployed on Sandbox then it needs to invoke http://www.sandbox.com/XXX while if in Production then it needs to use http://www.production/XXX.
Custom settings are what you want to use. This way you can have different configuration values in your sandbox and production orgs. Also, custom settings are cached at the application level, so accessing them is very fast.
Here is some more documentation about how to access custom settings from Apex code.