You confused me, and perhaps yourself, by using the element name "Customers" to represent a single customer. You can't sort the customers in the rule that processes each individual customer, it has to be done in the rule that processes the parent element. And your second template rule is wrong because it simply copies the input document intact without every firing the template rules for the children. You only need one template rule here:
Code:
<xsl:template match="xmldata">
<xsl:for-each select="Customers">
<xsl:sort select="CompanyName"/>
<xsl:copy-of select="."/>
</xsl:for-each>
</xsl:template>
Of course you can use an apply-templates if you want to do further processing of the customer elements, but if you just want to copy them, the above is simpler.