I use Ultimate voice recorder -
Ultimate Voice Recorder - Android app on AppBrain
records all calls quietly in mp3 or 3gp format. can be easyy converted to mp3 on pc if needed. the other side volume is low but still good enough to understand.
P.S. why does call recording threads always turn in to "legal" issue discussion? can't people stay technical here? Everyone can decide if it's "legal" for him to do it or not on his own. And, btw, if I'm recording the conversation for my own use, I can't care less if it's legal or not.