It seems the most cost-effective way to earn my PPL is to purchase my own plane (with the intention to keep it for quite some time). I believe I would therefore need to find a CFI that is certified for that aircraft type, correct?
You are sort of correct. For the ground instruction for your basic Private Pilot Certificate, it would not really matter. For the actual flight instruction, the CFI has to be certificated for the category and class of aircraft in which you are being trained by them. If the aircraft is a taildragger, high performance, and/or complex aircraft, the CFI will need an endorsement in their logbook from another CFI showing that they have been trained for that scenario. If the aircraft requires a type rating (which almost no trainer aircraft does), the CFI will need a type rating on their certificate in that aircraft as well. Those aircraft requiring a type rating are generally defined by the FAA as:
(7) Aircraft type ratings—
(i) Large aircraft other than lighter-than-air.
(ii) Turbojet-powered airplanes.
(iii) Other aircraft type ratings specified by the Administrator through the aircraft type certification procedures.
Remember, the above explanation applies to the instructor’s Pilot Certificate for them to have the privileges to act as PIC while flying. The instructor’s CFI certificate is a separate certificate allowing them the basic privileges of instructing. The categories and classes listed on a CFI certificate are a little more general than those listed on a Pilot Certificate. An instructor will need both certificates to give the actual flight instruction in flight in the air. Ground instruction is different.
Most people learn to fly in something along the likes of a Cessna 150, 152, 172, 177, or (in some rare cases) 182. The Piper Cherokee line is another popular trainer. Even Cirrus has a line of aircraft that are very suitable as trainers. Any aircraft around that size or smaller is a great start.
As long as the CFI has an ASEL (Aircraft Single Engine Land) class rating on their Pilot Certificate and an ASE (Aircraft Single Engine) rating on their CFI certificate, they can instruct you in almost all aircraft typically used as trainers. If the aircraft in which you want to train is a float plane, the instructor will need an ASES (Aircraft Single Engine Sea) class rating on their Pilot Certificate. If the aircraft is a multi-engine, the CFI will need a multi-engine class rating (AMEL or AMES) as well as have a Multi-Engine Instructor certificate. If the aircraft is a rotorcraft, that falls into a different category than the above aircraft. Gliders also fall into a totally different category. So do balloons.
One caveat is that some CFIs are limited to training students for the Sports Pilot Certificate, only. While a regular CFI can train students for the Sport Pilot Certificate, a Sport Pilot CFI can not train students for the Private Pilot Certificate. Although the hours acquired in one can apply to the other in the same category and class, the Sport Pilot CFI can only endorse students for that specific test and checkride.
For a more in depth description of aircraft category, class, and type ratings as they apply to pilot certificates, please see Title 14 of the Code of Federal Regulations (14 CFR a.k.a. the FAR/AIM) Part 61.5. Especially pay attention to Subpart (c) pasted below.
(c) The following ratings are placed on a flight instructor certificate when an applicant satisfactorily accomplishes the training and certification requirements for the rating sought:
(1) Aircraft category ratings—
(2) Airplane class ratings—
(3) Rotorcraft class ratings—
(4) Instrument ratings—
(5) Sport pilot rating.
With one notable exception, for any pilot to legally fly an aircraft, they must be rated for that category and class of aircraft. Some (generally larger) types of aircraft also require a type rating.
So, if you purchased a Cessna 172 (a very common primary trainer), your CFI would need to be rated for Airplane category, Single Engine Land class (referred to as ASEL). Like most small aircraft, no type rating is required.
Where the notable exception comes in is that a CFI can endorse another pilot (including a student pilot, like you) to solo in a specific type of plane. This allows you to complete the required solo hours before you can take the test to get rated for real.
One thing the other answers didn’t address is insurance. Your insurer may have additional requirements beyond the legal minimum, either to determine your rates or decide whether they will issue a policy at all. For instance, they typically ask the “total time” and “time in type” for each pilot on the policy, which will include your CFI. If your CFI doesn’t have enough (or any!) time in type, they may need to first get a few hours of instruction from someone who does before the insurer will let them teach you. So, if your plane is not a common one, it is probably best to check with a “type club” to find a CFI near you who already had the required experience.