First of all, we generally call the random per-encryption value Initialization Vector (IV) not salt in the context of block ciphers.
AES-256 has 128 bit blocks, so the IV should have 128 bits. Typical libraries that implement CBC mode have a special parameter for the IV. You shouldn't mix it into the plaintext yourself.
AesCryptoServiceProvider
creates a new random IV by default when you instantiate it. You just need to store it alongside the ciphertext and restore it before decryption. Since you need the IV to start decryption, I prefer putting it at the beginning of the ciphertext. But how and where you store the IV has no effect on security.
An additional hint beyond your questions: Add a MAC (e.g. HMAC-SHA-2) on the ciphertext. Be sure to compute it on the ciphertext including the IV (encrypt-then-mac), not on the plaintext (mac-then-encrypt). Else an active attacker can often use a padding oracle to decrypt the message. Don't forget to use a constant time comparison function for MAC verification.