There are a few ways malware can come preinstalled on the phone, which are varyingly detectable.
If you suspect the phone vendor will load your phone with malware, don't buy from that vendor. First, there's no guarantee you'll find any malware, and second, there's no guarantee you'll be able to remove it even if you do find it. Buy from a vendor you trust.
The phone comes with
EvilFileStealer.apk preinstalled and granted all permissions. It's doing malicious spyware/adware/etc. things using completely normal APIs and completely normal permissions; it's just that you, the user, didn't grant it its permissions. (Insert joke about Facebook here.)
Detecting and fixing this is the same as detecting and fixing any other malicious app. You could manually look through apps for stray permissions, and trim them down. Depending on the vendor, you might be able to do a "factory reset" to get rid of it. If the vendor hasn't marked the app as un-uninstallable, simply uninstalling the app is enough. Failing all that, if the phone can be rooted, you can install a stock OS, or an alternative, e.g. GrapheneOS.
You'll note all of those are conditional: A malicious vendor can lock you out of all of them, if they want. It depends how deep into this scam they get. That said, if they're just dumping a malicious APK on your system, I'd assume they won't bother going further -- someone investigating enough to notice the malware isn't part of their target audience, anyway.
I don't have hard numbers but I suspect these are the most common. Most users will never notice. Why bother with more advanced malware when it'll do?
One step up from a standalone malicious app is embedding malicious functionality into a seemingly normal app. For example, someone could disassemble the Facebook app file, insert malicious code, and reassemble the app, leaving you as the end user none the wiser. Externally it'll look just like Facebook, with the same icon, text, description, maker, etc.; internally it'll be malicious.
Depending on exactly how the "middleware" (heh) is being installed, this might not actually be possible. If they want it to look a lot like Facebook, they'll override the app verification logic, which will let them pass off their app as cryptographically verified. Otherwise, they can write the app's info to claim it's made by Facebook, which will probably fool most users. (This varies by platform, but would you notice that that Facebook app is made by Facebook, Inc. instead of Facebook Corporation?)
This can be detected by anti-malware software, and you might catch it looking for spurious permissions -- if they backdoored the calculator app, you might notice that calculator doesn't need to know your location or have access to your files. If they backdoored Files, you might not notice it shouldn't have access to your files. Removing it is similar to removing a malicious app, with the same caveats. Then presumably you'd want to install a non-malicious version of that app, assuming you can find it.
This is a significant step up from the previous two, but probably quite doable. In short, they take a normal OS, then add custom malicious code to it. It'd require someone to root the phone or buy from an OEM, basically taking the technological position of a typical phone maker.
This would be basically undetectable to your average user. You might notice behavior differences or weirdly slow updates, but both of those can just be normal vendor customization on Android, or inexplicable haunting common to every system. With sufficient logging on your firewall you might notice it phoning home, though at that point it might already be too late.
A forensic sweep could probably turn it up, if done correctly. Theoretically a malicious OS could e.g. subvert the adb protocol to present the OS differently, but that's unlikely. And you could desolder and directly read the actual memory chip. Comparing the system to a stock system of the same claimed version would narrow the search immediately, though you'd still have to dig through each difference to see whether it's malicious, and that could involve some very in-depth analysis.
From within the compromised OS, there's no even slightly reliable way to find it. You can check e.g. version and OS info to see if there's anything inconsistent with the real entries, but that requires the malware dev to have made a mistake and you to deeply understand all the possible correct values.
Getting rid of a malicious OS is hard; basically your only option is rooting the device (not necessarily possible on a malicious OS, even if it's doable for the vanilla version!) and reinstalling the factory OS or an alternative.
This would be quite difficult to execute, and correspondingly difficult to get rid of. In short, they'd have to either find a software-level way to change the firmware, or pull apart the phone and physically find the chip with the firmware on it. Any given part of the phone could support both, or neither, or just one; it depends on which part. The malicious firmware could then access raw device memory to snoop on you live, or examine your files, or many other things. It depends what firmware they replace.
Detecting malicious firmware is basically impossible, unless you're able to pull apart the phone, physically access the relevant storage chip, and reverse-engineer the whole thing. A factory reset probably won't fix it -- if for no other reason than a vendor sophisticated enough to rootkit your firmware will probably protect it from factory resets too. Firmware malware can also be used as an entrypoint to deliver other malware directly to your OS, or as an app.