Both algorithms, PBEWithHmacSHA512AndAES_256 and PBEWithMD5AndDES, first generate an encryption key by processing a password, a salt and an iteration count (using HmacSHA512 and MD5, respectively) and then encrypt the plain text (with AES-256 and DES, respectively) using this key and the CBC-mode. When the Cipher-instance is initialized, a pseudo-random initialization vector (IV) is generated that is required for the CBC- mode.
In the context of PBEWithHmacSHA512AndAES_256, the IV is generated using the SecureRandom implementation of the highest-priority installed provider, at least for the Cipher#init()-method used in the code (note that there are several overloads of the Cipher#init()-method and that a SecureRandom-instance can also be passed explicitly). I.e. with each Cipher-initialization a new (random) IV is generated and therefore the encrypted text is always different, even for an identical plain text. For this reason, the encrypted text in your examples changes in this context.
In the context of PBEWithMD5AndDES, the IV is only determined by the password, the salt, the iteration count (and of course the MD5-hash-algorithm itself). Therefore, the IV and the encrypted text do not change in case of repetition (provided that password, salt, iteration count etc. are the same). For this reason, the encrypted text in your example does not change in this context.
The generation of a new, random IV during the Cipher-initalization makes sense with regard to the following requirements for the IV: For security reasons, an IV in CBC-mode (btw this also applies to other modes) may only be used once under the same key. In addition the IV must be unpredictable.
PBEWithMD5AndDES is deprecated.
EDIT:
The use of an IV is standard nowadays (for security reasons). A lot of information can be found on the Internet on this topic e.g. here. In the following I will only describe a few basic things.
The IV used for encryption must be stored in some way because it is required for decryption. The IV does not have to be kept secret, so that it is usually concatenated with the encrypted data (e.g. before the encrypted data) and stored together with them. During decryption, both parts can be separated because the length of the IV is known (16 Byte for AES). E.g for the concatenation in the encryption-method something like the following is used (let iv and enc be the byte-arrays with the IV and the encrypted data, respectively):
byte[] result = new byte[enc.length + iv.length];
System.arraycopy(iv, 0, result, 0, iv.length);
System.arraycopy(enc, 0, result, iv.length, enc.length);
and in the decryption-method the corresponding counterpart (having in mind that the length of an IV in AES is 16 Byte).
In the encryption-method the IV can be determined with Cipher#getIV() (this must of course happen after calling Cipher#init()).
In the decryption-method you have to pass the IV to the PBEParameterSpec-ctor (e.g. let iv be the byte-array with the IV):
IvParameterSpec ivSpec = new IvParameterSpec(iv);
AlgorithmParameterSpec paramSpec = new PBEParameterSpec(salt, iterationCount, ivSpec);
The generation of an IV can also take place outside the Cipher-class, see e.g. Generating random IV for AES in Java. Then you have to pass that IV in the encryption-method in the same way as above described for the decryption-method.
Note, in connection with an IV some points have to be considered e.g. using a mode without an IV (e.g. ECB), using an IV consisting exclusively of 0-values, using a predictable IV or using an IV more than once under the same key etc. drastically reduces security in general, see e.g. here!
