Thanks Mike for your well thought out response.
I think thats a pretty good solution.
Currently, there are less then 300 users and about 5 "newsletters" -- the user base will expand slowly over time (maybe 50 a year) but I invision there being dozens of newsletters for various subsets of the userbase.
Just to recap and make sure I got all that, I should:
1) In the newsletters table, define specific parameters that easily match columns already set in the users table such as gender, age, and location.
2) If there are more complex parameters, have a column containing serialized PHP code to be run after the SQL query brings back a larger dataset that can be filtered via the PHP script, not the SQL.
3) Create a lookup table of specific users linked to specific newsletters for any newsletter that is not flagged as being open to everyone.