Originally Posted by Baywatch

ALLCallRecorder mentioned somwhere above worked for me on my crappy Motorola Cliq running a rooted Android 1.5.

Infact I was a bit surprised at the quality of the recording. The app itself could use some work, but it does work.

and yeah, the "wire-tapping" dood is a nub. One person notification is all that is required in all but a handful of states.

Example in my state the statue states clearly:
R.I. Gen. Laws §11-35-21(c)(3) - It is lawful to intercept a communication if one is a party to the communication or has received the prior consent of a party to the communication.