working under the table

What does that mean? Is it an idiom?

It means "working illegally" as far as I know.

Or it could be a euphemism for what certain prostitutes do.

It means that you are getting paid cash, and no one is telling the government, so you don't have to declare it when you do your taxes.