How does critical chance work?
Critical hits do extra damage; they do not guarantee hits. What I believe is happening is:
Xcom rolls a hit (using the next randomly generated number)
Xcom rolls to see if you hit some cover or some other enemy(??), if you missed.
Checks critical chance if it's applicable (Cyberdisc's in disc form cannot be critted, there may be other scenarios where Crits do not apply). I have no idea if you can crit cover but I sort of doubt it.
Calculates damage if and only if there is a hit, and then calculates it differently on a crit. If you miss and hit cover, it might also calculate damage.
So the possibly sequences would be:
Miss/--/--
Miss/??/?? affect some cover somewhere (or hit annother alien? Such things have been reported; one would expect damage to be rolled there)
Hit/non-crit/normal damage
Hit/Crit/crit damage
Once it calculates each of these things as needed, it shows you the results in game.
I know cover can be damaged/destroyed, but we need more data on what precisely is going on. Does cover have HP and are you taking away from that pool? Is it just reduced a step or possibly fully? I don't know. I have never observed a stray shot hit another enemy but that is entirely anecdotal and should be taken with a grain of salt. There appears to be no friendly fire on "normal" attacks (i.e. not using grenades or rockets). Observations in the comments suggest that the criticals are handled via a second roll; that is, you do have to roll to hit and then roll to see if you crit.
See Are Hit Chances Predetermined commentary on Xcom: Enemy Unknown's generation of random numbers.