AES is a block cipher: it takes as input a block (16 bytes, in the case of AES) and a key (16, 24 or 32 bytes, for AES), and outputs another block (again, 16 bytes). It is a fully deterministic algorithm, fully specified, and everybody in the world ought to obtain the same output block for the same input block and key.
However, you don't encrypt a block, you encrypt a message. The block cipher is only a building element; actual encryption uses a mode of operation which invokes the block cipher repeatedly. There are good modes, and there are bad modes; the goal is to achieve confidentiality of the message as a whole and not leak partial information, such as whether two parts of the message are equal to each other. In particular, if we are to encrypt two messages with the same key, we usually do not want to reveal whether the two messages were identical or not, so something has to change, somewhere, between the two encryptions.
Most modes of operation use an initialization vector which is where the non-determinism is injected. Some modes (e.g. GCM or EAX) require only a non-repeating IV; a counter can be fine for them, and can be implicit in some context (e.g. when there are successive messages on a given communication stream, the message number can serve as IV). Some other modes, notably CBC, are secure in all generality only if the IV is chosen randomly, uniformly, with a strong PRNG, and the next IV to use is not already known when the plaintext data is chosen. failure to meet all these requirements has been the source of many problems, e.g. the BEAST attack on SSL.
So one could say that secure symmetric encryption requires at least memory (for instance, to remember a counter value) or randomness. The "memory" can be a common worldwide counter (e.g. current time, but beware clock adjustments !).
If you are ready to tolerate the small leak about whether two given input messages are identical or not, then it is possible to have a fully deterministic, memory-less encryption system, but it will not be compatible with streamed encryption (you have to keep the whole message in memory during the process). Basically you compute a deterministic MAC algorithm over the message (such as HMAC) and use its output as IV. This is a two-pass algorithm, and that's rather unavoidable. If two source messages are identical, then they will yield the same encrypted message, but if they differ anywhere (even on their last bit) then, with high probability, the encrypted messages will be wholly different.
Unfortunately, platforms for which memory and/or randomness are hard requirements (e.g. smart cards) are also platforms where RAM is at a premium, and a two-pass system can be overly expensive.