If I wanted to create a PoW alrorithm to replace ethash on a private blockchain, how would I tell Parity to use it?
You can use Parity's Pluggable Consensus feature.
There is a list of provided engines to choose from, which require you to edit the chain specification files associated with the nodes in your network.
If you want to use your own bespoke engine, you'll have to write it yourself, then edit the chain specification files to point to it.
Parity comes bundled with a number of consensus engines. While the most widely used is the Ethash proof of work Engine, there are others which can be used for proof of authority or stake chains. The Engine is chosen by placing an appropriate entry in the "engine" field of the spec and providing the correct "seal" under "genesis" field, as described on the Chain specification page.