You can use either one. You can also use that. Finally, as J. Taylor pointed out in the comments, you may also choose to use no word in that position.
The most controversial to you seems to be the version with where. Here are examples of such constructions from published literature:
It reminded her of the pansies that bloomed in her aunt's garden, where she visited last summer. (source)
Today, she will bring us up to date on the current situation of China, where she visited last year. (source)
Boulette's Larder feels like someone's home, or perhaps a kitchen in Italy, where we visited last fall. (source)
Mr. and Mrs. Harry Howard, Mr. and Mrs. Harry Poett, and Miss Emily Carolan have returned from Santa Barbara, where they visited last week with Miss Sarah Redington. (source)
Instead of going downwards back to the cave where they visited last night they went upward. (source)
I have… submitted to the Public Housing Administration a development program for the McKees Rocks area adjoining the area where you visited yesterday. (source)
In the last two, the where clause is integrated into the structure of the sentence, whereas in the others it is a supplement, as indicated by the comma that precedes it.
The choice of which, that, or no word vs where depends on whether visit is taken as a transitive or an intransitive verb. Note that visit has both transitive and intransitive senses, see e.g. here, here, … In its intransitive sense, visit means to make a visit.
Analysis of the various options
We have four options. All four are relative constructions. Two are wh-relatives (with which and where), and two are non-wh relatives, one with the subordinator that, and one with a bare relative.
In the version with where, the verb visit is taken as intransitive. In the other three versions, it is taken as transitive.
 We enjoyed the islands [which we visited last week].
This is a relative construction, and the part in the brackets is a relative clause. Simplifying matters somewhat, the pronoun which serves as the object of the verb visited, except that it has been fronted i.e. moved from its usual position after the verb to the front, to a 'prenuclear position' (i.e. the position 'before the subject + predicate construction that constitutes the nucleus of the clause' (CGEL, p. 1037). The antecedent of which is the nominal islands (without the article). In particular, one might say that 'embedded into'  is the following clause: We visited (some) islands last week, where (some) islands is the object of visited.
CGEL indicates these facts as follows:
We enjoyed the islandsi [whichi we visited ____i last week.]
The '____i' is called a gap, and there are technical reasons why we consider this gap as what really serves as the object of visited. The relative word which is, on the one hand, linked to the gap, and on the other hand, it has islands as its antecedent. We use the subscript index i to indicate these relationships. According to CGEL (p. 1038), 'prenuclear elements that are linked to a gap are interpreted as having the function of that gap, and we can thus say in a secondary, derivative, sense that they have that function.'
 We enjoyed the islands [where we visited last week].
The grammar of  is completely analogous to the grammar of
[2a] We enjoyed the islands [where we slept last week].
The structure of  is indicated as follows:
We enjoyed the islandsi [wherei we visited last week].
Note that this time there is no gap, because visited is taken as an intransitive verb, just like slept.
According to CGEL (p. 1050), 'where takes locative expressions as antecedent; within the relative clause it functions as adjunct of spatial location, goal complement, or complement of a locative preposition.' Further, CGEL provides an analysis of the sentence
 She wanted to see the house [where she had grown up].
A 'double-variable' representation of  is "She wanted to see house x; she had grown up in x": the "in" component is contributed by where together with its spatial location function, with the antecedent determining the value of the variable x.
The corresponding double-variable representation of  is "We enjoyed islands x; we visited on x last week."
The correct preposition that is contributed by where is on. Here are related examples of such usage from published literature:
He had visited on the Island of Elba that was Napoleon's home during his exile. (source)
…Creeley' s relationships with painters some of whom visited on the island… (source)
 We enjoyed the islands [that we visited last week].
Here the structure is
We enjoyed the islandsi [that we visited ____i last week.]
Note that visited is here taken in its transitive meaning, and the function of the object is again performed by the gap. So this case is quite similar to the which case discussed above. One difference, according to CGEL, that is not a pronoun here, but a subordinator (pp. 1056-1057), which is why it doesn't get a subscript index i. This case is closely related to...
4. bare relative
 We enjoyed the islands [we visited last week].
This is obtained from  by omitting the subordinator that. The structure is
We enjoyed the islandsi [we visited ____i last week.]