What does an apprenticeship entail and can an apprenticeship be undertaken for any skill?
Also, who should I go to if I were to become an apprentice in a skill (For example religious skills if possible)

two seperate things here: The Apprentice Pseudo-skill and IC apprenticeships.

The Apprentice Pseudo-skill is available to anyone who has spent none of their XP (including the base 8 you start with). This allows you to be mentored by a character to effectively use their skill to let you do things. This lets you try out parts of the game.

IC Apprenticeships are more fluid. You don’t need to be taught a new skill you can just learn it ‘off screen’ as it were, However it can be good fun, for both you and your teacher to learn IC. this is going to depend on what nation you’re from but in general talk to people with the skill in your nation and see what they want in exchange for their time. For religious skills in particular you could try to find your national assembly, or if you have a particular Virtue in mind you could go to the hub and see if you could catch a virtue assembly meeting and if (like me) you keep missing them their are lists of Priests on the board so you could pick a name that catches your eye and try to find them. In your nation your Egregore may be able to help you look at the right people and in the hub the Tribune of the Synod is normally around and could point you likely in the right direction.