I've read that the most commonly used verbs in a language are almost always irregular, and for the most part the irregular forms of verbs can be traced to an archaic form being preserved in the language, or to the influence of other languages. When creating a naturalistic conlang, what verbs should be irregular? I'm already aware that 'to be' is almost always irregular, but are there any general patterns for which verbs are most often irregular in a natlang? (For example, are verbs involving movement more commonly irregular than not?)
The first class of verbs that is often highly irregular are the auxiliary verbs. This does not only comprise to be and to have but also the modal auxiliaries (like must, can, shall, and will). They are used very frequently and tend to erode phonetically, and they are also prone to suppletion (showing a mixture of different stems from originally different words).
A quick check (for my native language German) seems to confirm your intuition that verbs of motion are more often irregular than average. They are also used quite frequently. In Romance languages, the basic verb for to go (e.g., French aller or Italian andare) is very irregular and mixing several different stems ((vulgar) Latin ambulare/allare, vadere, ire).
Some verbs are irregular because they rhyme with an irregular verb, e.g., German schreiben, schrieb, geschrieben "to write", borrowed from Latin scribere, became irregular because of rhyming verbs like bleiben "to stay".
Well, the statement is demonstrably untrue. Chinese (Mandarin and Cantonese) doesn't have irregular verbs, because verbs aren't conjugated. Quechua doesn't have any. And languages like Inuktitut has no irregularity in verbs because of the way that the language assembles words based on a root+affixes.