just throwing in my 2 cents...
Yes, switches can use STP if it's enabled on them, and that only really needs to be the case if you have a network topology susceptible to routing loops. If you use vlans, the switch could also recognize that it's connected to another switch if you enable vlan trunking on one of the interfaces.
Now if we're talking cisco proprietary networks, then they'll be able to use Cisco Discovery Protocol to find directly connected cisco devices and information about them (type/version#/ip/etc).
There's more that can be said about the mac address table (which isn't arp), and looking to see if it multiple ip's show up as the same mac address (leading us to assume that those multiple devices are connected by another switch)...
...but now going back and reading boris's original question, if it's something like, "given a pretty barebones network topology with pretty much 2 switches connected to eachother, how do they determine if the <cross-over or straight-through cable> is right for their setup based on the pin connections?" from a couple minutes of looking, it seems that most modern nics use "auto sensing" or "Universal Cable Recognition". I haven't come across an article yet that describes exactly how it works, but my guess is that as soon as a packet goes across the wire for the first time, the NICs on the switches sense which pair of wires were used to transmit and auto-adjust themselves for the correct configuration to listen on those pins and transmit on the others.
This link mentions auto-sensing towards the bottom: Ethernet crossover cable
ok, n/m, i went back and read again and don't think that was what boris was talking about in the first post....