Hello,
The online help built into the controller is good to guide you but in brief.
If you are on a pretty recent sw level then you will be able to do it, otherwise you may need the advanced voicemail license.
Create a hunt group and the type will be recorder, add some of your vm port directory numbers into it.
As you said set up the record a call key on the handsets you need.
In the class of service of the phones you want to use it, set record a call to yes.
And....you should be good to go! Don't think i have missed anything obvious
When you log into you vm box it will tell you if you have any record a call messages then.