AES encryption/decryption using pure .NET and streams
Let's talk about your code then we'll talk about that paragraph of text you have.

First off:


Using   aes As System.Security.Cryptography.Aes = System.Security.Cryptography.Aes.Create(),
        ms_unencrypted As New IO.MemoryStream(unencryptedData),
        ms_encrypted As New IO.MemoryStream()



This is largely not pleasant to read. You have ms_ hungarian (IIRC) notation, and you have everything aligned funky, and it's just visually unpleasant. Let's fix that:

Using aes As System.Security.Cryptography.Aes = System.Security.Cryptography.Aes.Create(),
    unencryptedStream As New IO.MemoryStream(unencryptedData),
    encryptedStream As New IO.MemoryStream()


Alright, that doesn't do much but it does start pushing things into motion.

You state in your question:


  I want to take advantage of streams if possible


But the API doesn't use any streams! It requires you to pass a byte[], why not allow streams to be used? Then you eliminate that unencryptedStream in Encrypt and the encryptedStream in Decrypt entirely. Let the caller deal with the stream mechanics.

Next, why not allow the caller to get a Stream back out? You still force the caller to deal with a byte[] in the end, we could eliminate that.

Public Sub Encrypt(key As Byte(), unencrypted As MemoryStream, encrypted As MemoryStream)
    Using aes As System.Security.Cryptography.Aes = System.Security.Cryptography.Aes.Create()
        Using cs As New Security.Cryptography.CryptoStream(encrypted, aes.CreateEncryptor(key, aes.IV), Security.Cryptography.CryptoStreamMode.Write)
            encrypted.Write(aes.IV, 0, aes.IV.Length)
            unencrypted.CopyTo(cs)
        End Using
    End Using
End Function


Now you have no responsibility for the streams, but once we see this we could also build a version that takes a byte[] and returns a byte[] to wrap this version. Then our API is clear, concise, and robust.



And then there's this paragraph:


  I've read that it's good practice to generate a random key. If I do that, then both the server and the client would need to know the same key. I assume this would then mean that I'd need to transmit the key in the call to the web-service from the client. Is that correct? Is that secure? I'd assume that the call to it would be done via HTTPS, but is there anything else I'd need to be aware of in that scenario?


While HTTPS is good and all, using AES to encrypt data between a server/client is not really a great idea. Encryption has the concept of a 'public key' and a 'private key', some algorithms use both, some only use one. In the case of AES, it uses one key: a private key.

The names themselves should give things away, but I'll be explicit anyway:


public key: This key can be shared with anyone, and should be available for all persons wishing to use the system.
private key: This key should be kept as secret as possible, and not shared unless absolutely required. This is the key that, without which, attackers cannot easily reverse encryption.


Now AES uses only a private key as both encryption and decryption. This is known as symmetric encryption or a symmetric encryption algorithm. What you are discussion requires something else, known as asymmetric encryption or an asymmetric encryption algorithm.

These algorithms come it two major variants: those that use the public key for encryption and the private key for decryption, and those that use the private key for encryption and the public key for decryption.

The option you pick depends on your use-case. In the case of something being shared from server -> client, you would pick an algorithm that uses the private key for encryption, since the server is entirely under your control. You can keep things on it a secret. You cannot keep things on the client a secret, so it should get a public decryption key. Then to send data back you should have a second algorithm that does the opposite, and uses the public key for encryption.

The next option is to have the client establish a connection to the server, then use a public key encryption algorithm (such as RSA - where the public key is the encryption key) to send it's AES key. Then you can use AES for the remaining communication between the server and the individual clients. This is the most common type of scenario with RSA, as it's very expensive to use for encryption and decryption.

If you're using HTTPS, however, there's no need to build a sophisticated mechanism to further encrypt your information. HTTPS already provides a secure communication session between client/server, though it doesn't hurt to add more security in general, it can have drastic performance impacts if done wrong or 'over the top'.