If I wanted clients to identify themselves how can I issue them client certificates? Does it matter whether they are using Windows or Linux or whether it is a mobile device? What information do I need to provide to Certificate Authorities?
It depends on the CA you choose. There are CAs that will happily issue client certificates just by validating an email address. Generally, certificates are issued for signing emails, encrypting emails, and identifying a client. In all three cases, you basically just want to associate a key with a person identified by their email address.
StartCom's free CA doesn't really mention it anywhere, but they offer free client certificates. The process is precisely the same as the process to get a free SSL certificate, and you can use the same account for both. WoSign has a similar system, as do many other CAs.
If you just want a validated email address for your own use, you don't need a CA at all. Just validate the email address with a click-through email and issue the certificate yourself. Obviously, you'll be the only entity to accept that certificate as proving anything, but if that's all you need, so be it. StartCom does this too. Log into their system and watch it generate a certificate for you and then use it to log you in.