Rashi (Pesachim 2a) and Ran (Pesachim 1a) maintain that bedikas chametz is deoraisa. Tosafos (Pesachim 2a) argues that it must be derabanan, as one can technically avoid owning chametz by being mevatel (nullifying) it.
The Bach and Magen Avraham (OC 431:1) write that one should begin one’s search after shekiah. Most follow the Mishna Berura (431:1), however, who writes that one should begin promptly at nacht. One should not learn or eat (a meal) for half an hour beforehand, as doing so may cause one to forget to search. While the Mishna Berura (431:8) brings reasons both for and against davening Maariv first, he maintains that ideally one should.
While one needs to search all of one’s cupboards, too (unless they are being sold), one can rely somewhat on them having been checked previously (Daas Torah 433:2; Shaar Hatziyun 432:12).
Many follow the Arizal’s minhag of having someone else hide ten pieces of chametz around the house before bedikas chametz. The Taz (OC 432:4) dismisses this custom and writes that one should not do so, out of fear that one may get lost. Nonetheless, the Mishna Berura (432:13) writes that one should not abandon this minhag, and in Shaar Hatziun (432:12) writes that when one has already checked the house for chametz, one must hide a few pieces in order to avoid making a bracha levatala. It also serves to encourage one to check properly around their house.These pieces should be small (less than a kezayis), sealed in a plastic bag, and their locations recorded to avoid any being lost.