Deck checks must be performed at all Competitive and Professional Rules Enforcement Level tournaments, and the Head Judge has the option to perform deck checks at Regular Rules Enforcement Level tournaments. At least ten percent of all decks should be checked over the course of the tournament.
Note that this is a recommendation. Even though deck checks are very important, the tournament always has priority. Floor coverage should should take priority over checking decks. Deck checks are a way to attempt to foil certain forms of cheating. The biggest factor is that they act as a deterrent, discouraging players from doing anything dishonest with their deck, since deck checks are going on.
A full deck check should not be performed if a player has drawn an opening hand and potentially made mulligan decisions.
Please note that this is a change! While in the past it was simply recommended that a check not be done once a player has drawn their hand, now it is stated that no full check should be performed. Realistically, unless there is some greater reason for those particular players, it is better to simply choose a different match to deck check.