Does chemical bonding decrease the entropy of the universe? I have read in many credible texts ( including "a brief history of time" ) that nature always increases entropy, that is, the entropy in the universe increases. But I learnt that atoms and molecules form bonds to attain stability by filling their orbitals.
So doesn't this violate that entropy should always increase. I mean if all the atoms are trying to attain stability ( order ) then why does entropy ( chaos ) increase?
 A: The formation of chemical bonds releases energy, which heats the universe, which increases its total entropy more than enough to compensate. 
As an example, consider the oxidation of aluminum (Al) in air, which occurs essentially immediately. Every chunk of aluminum you've ever seen has been coated with an oxidized layer (alumina, $\mathrm{Al}_2\mathrm{O}_3$) with a thickness of at least a few nanometers. But, as you imply, why would the oxidation reaction 
$$4\mathrm{Al}+3\mathrm{O}_2\to 2\mathrm{Al}_2\mathrm{O}_3,$$
occur spontaneously? After all, it involves the conversion of oxygen gas to a solid, which requires a notable decrease in entropy (630 J/K per mole of product; gases carry a lot of entropy because the molecules are free to move around with a variety of positions and speeds).
The resolution is that the reaction is an exothermic one that heats things up (the sample and the surrounding environment). That is, the bonds release energy as they form. The formation of alumina releases about 1700 kJ for the same mole of product, which heats the sample and its surroundings, which in turn increases their entropy (by around 5600 J/K) because the molecules can assume a wider range of positions and speeds. As a result, the general rule of total entropy maximization for all spontaneous processes still holds true.
A: All the statements about the entropy of the universe share a common problem: there is no way to measure such a quantity (to check this statement, try to list all the known experimental methods to measure entropy differences and you can decide if they could be applied to the entire universe). Even the theoretical definition is not very easy. There are many definitions of entropy, from thermodynamics, from statistical mechanics, from information theory, from theory of complexity, from dynamical system theory, ... and they are not all equivalent or they become equivalent only under additional conditions.  Which one could be  applied to the universe? And one is speeking about the equilibrium entropy or some non-equilibrium extension of the concept? The former looks questionable, unless one is convinced that we live in a universe at equilibrium. The latter goes back to the problem of which definition to use.
In thermodynamics people are used to speak about a "thermodynamical" universe which is the union of a particular system plus the surrounding environment, provided such environment could be well characterized from the thermodynamic point of view. For example, system+environment could be an  isolated system. Such thermodynamic "universe" is less problematic as the whole known universe.
Much more on the earth, the presence of ordered structures in interacting systems is not in contradiction with the principle of increase of entropy, once one remembers that such principle is valid only for an isolated system at fixed energy, volume and number of particles. Under such constraints it is possible to find macrostates where the majority of the underlying microstates corresponds to ordered configurations.
