EDIT 2012-10-22
You can enable Record Macro as follows:
3.5.x
Menu Tools > Options > LibreOffice > General
Enable experimental (unstable) features.
3.6.x (see comments)
Menu Tools > Options > LibreOffice > General
Enable macro recording (limited)
EDIT 2012-11-29
4.0.x (LibO-Dev 4.0.0.0.alpha1)
Menu Tools → Options → LibreOffice → Advanced
Optional (unstable) options
Enable macro recording
(see also → Release Notes 4.0)