Yes, Deck Verified on Steam means Valve has verified that it works on the Deck. If it works on the Deck, it’ll work on Linux, because the Deck runs Linux and it’s basically the same software stack.
Protondb is a community project where people submit reports about what works and what doesn’t. It’s a good resource, but only really needed if something isn’t working right out of the box.