With modern technology, the government can track what people are buying.
One method to do that is to create a database of all purchases made with credit cards or checks. This way you can see if someone never buys meat products.
If people use cash, the government can also enforce a mandatory customer card (mix between ID card and loyalty card) policy. The citizens will have to present this card for all food purchases, in shops and restaurants.
The problem with this method is that people could buy meat and then throw it away.
A solution would be to ask restaurants to take note if someone didn't eat the meat products in their plates, and signal it when editing the bill (this plus the customer card will immediately give you the names of the picky eater).
To accelerate the process and be sure people too poor to eat out won't stay off the grid, restaurants and shops around the country could sell small meat balls or chunks of jerky at the counter. The cashiers would validate the sale only after the customer put it in their mouth.
If the meat bits are cheap enough the government can make weekly public meat-eating mandatory to all citizens.
The advantage of these solutions is that they won't cost too much. Data mining will give you lists of potential vegetarian (people who only buy the legal minimum amount of meat products), and most of the policing part will be done by the citizens themselves (cashiers, waiters, etc.).