One of my daughters in Seattle called me after Washington state legalized Marijuana. She said that a lot of companies did a lot of random drug tests the day after it was legalized, focusing on employees they were looking to get rid of. It is still federally illegal, after all. Apparently a LOT of people were fired.
It doesn't have to be illegal at any level for employers to test; some employers test for tobacco use.