Is cold storage a wallet or a private address?
Neither. Cold storage is bitcoins that are sent to an address that was generated from a private key that has never been connected to the internet.
First what is the difference between a wallet and an address.
At the most simple level, a "wallet" is a collection of one or more private keys. Usually a wallet contains the bitcoin address that is associated with each private key (so that the address doesn't need to be re-generated every time you want to use it. Software wallets usually also contain features that take care of all the technical aspects of creating transactions, and provide an easy way to determine how many bitcoins the wallet has control of. Software wallets can contain additional features at the discretion of the developers of the wallet.
An address is the public information that you need to share with the person that will be assigning control of some number of bitcoins to you.
Is a wallet an address or can a wallet hold several address's?
A wallet holds one or more addresses (more specifically, one or more private keys).
When someone says that they got change from a wallet, don't they really mean from a public address?
No, they really mean "from a transaction". Transactions provide, as their inputs, a list of "unspent outputs". The act of including the output in the list of inputs to the transaction means that it is then "spent". The total value of all the inputs in the list are available to the transaction to be assigned to a new list of one or more unspent outputs. Any value from the list of inputs that is not specifically assigned to an output becomes a transaction fee that can be assigned to the block reward by the miner that confirms the block. Therefore, if the amount that is being "sent to someone" is less than the total value supplied by the inputs, the creator of the transaction must assign the excess back to an address that they have control over (a "change address").
why would anyone want to put change into a wallet that had coin in it that can be used to try and track your paths?
I'm not sure, but I think you're asking why someone would want to send the change back to an address that they previously used for receiving bitcoins? If that is your question, then some people like being able to track their balance and backup their access by keeping track of only a single private key and address pair. They seem to think this makes things easier.
Why doesn't all change go into a new public address.
The bitcoin protocol doesn't care where the change goes. It is up to the creator of the wallet software to decide how they are going to handle the excess value in the transaction.
when do you use your private address?
There are no private addresses. There are private keys. The wallet software uses the private key to generate an ECDSA signature when spending previously unspent outputs that were received at the address. This is how the wallet software proves to the entire network that it is allowed to spend the output.
So we have to check with a merchant to see where they are going to put change or can we tell them where to put it?
The person that is sending the bitcoins decides how to handle the change for the transaction that they are sending (or more specifically, their wallet software decides for them.
