Making array immutable

In my opinion, the mutability depends on two things: How many instances you would require if the object were to be immutable, and whether or not an immutable copy would ever be reused.

The first is easy, you don't need to make every permutation of a deck, you can just make a new one when needed, so that's not something which stops you from making it immutable.

Where I start to see a problem is the reusability. You make a deck immutable, but if the immutability only serves to provide a brand new object and throw away the old, it seems more logical to just mutate the object in place and not be creating unnecessary ones.

I do however see a definite use of immutable cards; There will only ever be 54 of them and they can definitely be reused. So what I would do is store a cache of those cards in an immutable List or Set:

private static final List<Card> CARDS = Collections.unmodifiableList(new ArrayList<Card>() {{
    //store all your cards, can be done without double-brace initialiation
}});

From there (in the context of being inside Deck), we can make a copy of this List without costing much memory at all - the Card instances will be the same since Java is "pass-by-value-of-reference".

//Note: The left hand side is purposefully LinkedList and not List, you'll see why
private final LinkedList<Card> shuffledDeck = new LinkedList<>();

public Deck() {
   this.shuffle();
}

public Deck shuffle() {
    this.shuffledDeck.clear(); //wipe out any remaining cards
    this.shuffledDeck.addAll(CARDS); //add the whole deck
    Collections.shuffle(this.shuffledDeck); //Finally, randomize
    return this;
}

public Card pop() {
    return this.shuffledDeck.pop(); //Thanks Deque, which LinkedList implements
}

This leaves you with the saved memory from making Card immutable, whilst not costing you numerous Deck objects.

The biggest problem is that you have a mutating method on the Deck class. You DO need to be able to mutate the cards you have in a deck during a game, but you actually don't need to mutate the actual Deck object for that. Suppose that you have an immutable card class and an immutable deck class. The deck is initialized with a full complement of cards. When you need to play a game you ask for a list of the cards that the dealer will be able to interact with, modify, etc. So the Deck class only really needs to hand a copy of the internal list out. That way the Dealer isn't modifying the internal list and the Deck is ready for a new game when requested and it doesn't matter that the copied list holds references to the same card instances as the internal Deck class since the Cards are also immutable.

public final class Card {

    public enum Suit { HEART, SPADE, CLUB, DIAMOND }
    public enum Value { ACE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE, TEN, JACK, QUEEN, KING }

    private final Suit suit;
    private final Value value;

    public Card( Suit suit, Value value) {
        this.suit = suit;
        this.value = value;
    }

    // ... rest omitted
}

public final class Deck {

    private final List<Card> cards = new ArrayList<>();

    public Deck() {
        for (Card.Suit suit : Card.Suit.values()) {
            for (Card.Value value : Card.Value.values()) {
                cards.add(new Card(suit, value));
            }
        }
    }

    // Get a new list of cards (though the actual card instances are the same
    // that's ok since they are immutable)
    public List<Card> getCards() {
        return new ArrayList<>(cards);
    }
}

Also since no state is being shared and the Deck is no longer mutable, then thread safety is no longer a concern. Another bonus of using a list of cards for the dealer is that there are built in sort (if you had card implement comparable), shuffle, etc, via the Collections class.

Edit: added after reading your comments:

If you want the Deck to hold state then you cannot have it be immutable. It can be implemented a number of different ways. Even though an ArrayList is a fairly large data structure compared to an array in almost all cases the use of it is better than a LinkedList in performance and is better than an array for safety and ease of use. If very, very high level performance is required you can get better with a primitive array (maybe) but the Collections API is quite optimized and the JVM is also extremely good at optimizing code on the fly. In my professional experience so far I have yet to run into a case where I would use an array over a list simply due to performance. In general I would say that is a case of premature optimization (beware of that). Though it makes sense in an abstract sense to use a Stack over an ArrayList, I would argue that the convenience of the built in shuffle method for lists (in Collections) would override that.

Using the same Card objects as above, the mutable Deck could look as follows (with a list):

public class EmptyDeckException extends RuntimeException {

    static final long serialVersionUID = 0L;

    public EmptyDeckException(String message) {
        super(message);
    }
}

public class Deck {

    private final List<Card> cards = new ArrayList<>();

    public Deck() {
        for (Card.Suit suit : Card.Suit.values()) {
            for (Card.Value value : Card.Value.values()) {
                cards.add(new Card(suit, value));
            }
        }
    }

    public void shuffle() {
        Collections.shuffle(cards);
    }

    public Card pop() {
        if (!cards.isEmpty()) {
            return cards.remove(cards.size() - 1);
        }
        throw new EmptyDeckException("The deck is empty");
    }
}

And if a stack is insisted on, then it could be like this:

public class Deck {

    private final Stack<Card> cards = new Stack<>();

    public Deck() {
        for (Card.Suit suit : Card.Suit.values()) {
            for (Card.Value value : Card.Value.values()) {
                cards.push(new Card(suit, value));
            }
        }
    }

    public void shuffle() {
        // Now this needs to be done manually and will probably be less performant
        // than the collections method for lists
    }

    public Card pop() {
        return cards.pop();
    }
}