What, if anything does a NCAA college coach have to do to redshirt an athlete? Is there an official document or paperwork required to be sent in to the NCAA? What does that process look like?
Athletic Director's office registers all athletes at school for all sanctioned sports (NCAA doesn't care/govern club sports) - this may slightly vary by school but how it worked at the school I was affiliated with. Each athlete is registered with a code. For incoming freshman they must be declared a redshirt before a specific date in accordance with that specific sport.
Coaches are more likely than not to register a freshman as a redshirt because it doesn't hurt. Athletes can be unredshirted instantly. The school would only get sanctioned if they tried to cover up an athletes activity to keep them redshirted. The reason why all freshman aren't redshirted is that a coach may know they want to play someone, the coach may fear that the athlete would be unhappy and leave, or the coach just wants a certain amount of turnover.
Now when a freshman athlete comes to a campus they have one of 3 statuses (forgive me if I mishandle the exact names).
Eligible - fully eligible for practices and game activity. This athlete you would have to notify the NCAA of their redshirt request.
Academic redshirt - based on their test scores (ACT) and high school GPA and a lot of hocus pocus the NCAA has a "grey area" where an athlete can retain a scholarship and practice but is not allowed to play in a game. This person could not be instantly redshirted for football (or any 1st semester sport) but in basketball this might happen if the student fixes things in the first semester.
Ineligible - student can't practice or play or receive scholarship money.
The other (that is 3 now) redshirt is a medical redshirt. If hurt before the first game the NCAA pretty much grants any freshman a medical redshirt. If it is after the first game the student must apply and more NCAA hocus pocus happens. And then there are students who have had two medical redshirts happen. So a redshirt freshman then sophomore.