Based on my recent experience, it seems they send the free anniversary night certificate immediately after you pay the statement that comes after the one your annual fee is charged on.
AF posted on February statement. Paid.
Only regular charges on March statement. Paid March 4.
Certificate in my email this morning. March 5.
I'm using the cert for a stay in May, so I may try to cancel for a prorated refund after that, or I may keep it just for Hilton stays depending on what my travel schedule looks like this year.