How do I add a new admin with full access to the fortigate using FortiOS CLI?

Did you read your documentation in the technical guide?

Here's the cli cmds assuming the default admin-access profile still exist;

config system admin     edit "youadminnamehere"

      set accprofile "super_admin"   for access users profile       set vdom "root"

      set password "pickastrongpassword"

end

fortinet techguide guide link 5.0

http://docs.fortinet.com/d/fortigate-cli-reference-pdf