Android ApplicationsAll the information you could ever want about Android Applications. Learn about apps and get help with them... all here! New apps can be found and announced in the Applications Announcements forum linked below.
Lots in the market. Recordroid comes to mind but I use one that just says recorder.
Before you download be sure to screen what it asks to allow access to and check out the reviews. The paid ones are a little better and have less adds/ access.
There are apps in the Market, however it completely depends on what phone you have. Some phone's hardware will allow you to record both sides of the call, some phones will only let you record one side, and some phones wont let you record at all.