The contract you write as the token-managing contract would be the one who controls how it's minted. Most basic token contracts/examples mint a certain number of coins at the beginning and then no more. The Unicorn token, by contrast, created no tokens when first created, and instead creates new tokens when someone donates to the Ethereum Foundation.
If you want to create a proof-of-work logic (e.g. SHA3 must be below some threshold difficulty, similar to Bitcoin), you'd need that as part of the token-managing contract, in the most basic setup, and then it would be the one "mining" (or "minting", whatever verb you want) the new tokens.
A more advanced setup would allow things to be changed down the road. The Unicorn token contract is not that smart in and of itself, but it has an owner that is another smart contract that is very complex. The owner of the Unicorn token contract is a DAO contract, where the Ethereum Foundation members can adjust the price per Unicorn, and it's actually that parent contract that you pay if you want a Unicorn, and the Unicorn token contract allows the parent to mint more tokens whenever the parent wants.