To extend Edward's excellent idea...we've had a seminar at our dojo and put signs and flyers out inviting the public to come by, watch and take home a flyer. We're doing it again next month.
Another thing we've done that no one has mentioned is to slip dojo business cards in aikido books in local bookstores.
We sometimes schedule weapons work at local parks. It's good advertising and it helps develop poise in students.