In light of Rex Tillerson's firing, why does the Senate have to approve a cabinet member's hiring, but not their firing?
Simple Answer: The Constitution Says So
The simplest answer is because the Constitution requires the Senate's approval before certain officials are hired, but doesn't mention them being fired.
From Article 2, Section 2:
... and he shall nominate, and by and with the Advice and Consent of the Senate, shall appoint Ambassadors, other public Ministers and Consuls, Judges of the supreme Court, and all other Officers of the United States ...
Okay, but why?
Federalist paper #76 discusses the appointments clause. The goal is to design a system "to promote a judicious choice of men for filling the offices of the Union". If the goal is to fill high positions with the best candidates, you need to make sure the hiring process is great - not the firing process.