On the <portal:mojoMenu control in the theme.skin file, set the SkinID to SiteMenu. Once you do this, the <portal:SiteMenu control should start pulling in your settings from the <portal:mojoMenu SkinID="SiteMenu" .../> control from the theme.skin file.
The skins contained within your SiteID directory may not have settings Joe A.was referring to because they are probably old versions of those skins. The skins contained in \data\skins are updated with mojoPortal upgrades so you should use those for reference. You should be working within your SiteID directory for skinning. The skins in \data\skins can't be assigned to individual sites. Those files are there so when new sites are created, they can be copied to the new site.
The theme.skin file must be in the root of your skin directory. For instance, if your skin is named MyCoolSkin and your site ID is 4, the path to your theme.skin file is \Data\Sites\4\Skins\MyCoolSkin\theme.skin. .NET looks for the theme.skin file in the /App_Themes directory so mojoPortal uses what is called a VirtualPathProvider to tell .NET where to find the theme.skin file for a given skin. VirtualPathProviders do not work under .NET 3.5 Medium Trust hosting so when using .NET 3.5 with Medium Trust hosting, you have to place your custom theme.skin file in the /App_Themes directory. VirtualPathProviders work in .NET 4 Medium Trust hosting so if you're running .NET 4 you can pretty much ignore this entire paragraph.
As far as you running in Medium or Full Trust hosting, it really has nothing to do with your administrative access to the server. You can easily determine the trust level by clicking the "System Information" link in the Administration menu.