Yes, you certainly need to check local regulations. In the UK there is quite a difference between being a private or a corporate/institutional user, for example. This is largely because regulatory compliance tends to apply to corporate bodies rather than individuals.

http://www.retellrecorders.co.uk/legal/home.htm

I believe the reason for recording a call might also be relevant. For example in the UK, answerphones, voicemail, and telephone ordering systems are perfectly legal and require no notification. The user expects the call to be recorded.....that's what they want.

Over here all you basically have to do if the legislation applies, is inform the caller that the call may be recorded.