As far as implementation goes, I think one of the simplest (but still efficient) ways of storing walls is using a two-dimensional array. Assuming we have an m by n map (that is, a rectangular map with m tiles on the 'x' axis and n tiles on the 'y' axis), then we will need two arrays, one m+1 by n for the vertical walls and one m by n+1 for the horizontal ones. I did a crummy drawing trying to illustrate this here:
Note that you get six rows of 7 vertical walls each in this example, and 6 columns of 7 horizontal ones. Also note that the walls on the border are coloured differently (red for vertical ones and yellow for horizontal). The border walls might, in some games, be unnecessary. The game code could just assume that all border edges are walls, so you wouldn't need to store them. Some games, however, might not. You might want to load another map if the player walks beyond the edge of the map, for instance. Or you might want to be able to store different types of walls, such as a wall with a switch or a niche or even just have more than a single artwork for the wall. Anyway, if the smaller array was to be used, you would need an m-1 by n array and an m by n-1 array.
It is also possible to make our solution more space efficient by using a "sparse" array, that is, an array that doesn't need to store every value, but has an assumed value (usually 0) if a specific one is not found. One way to do that is by creating a heap-sorted array of wall indexes. Since (usually) the size of a specific map is constant, although we usually think of wall positions as a two dimensional array, it is possible to convert it to a single, unique index. In a 0 based array system, a vertical wall on position (x,y) (assuming position (0,0) exists) could be given the index (y*(m+1))+x-1. By storing these indexes in a heap-sorted array, it is possible to find a given index in O(log((m+1)n) operations, which is still a loss from the immediate indexing of the simple 2d array, but not a big one. As long as your map wouldn't have many walls to begin with, the extra overhead of the indexing would pay off. One aspect that might be confusing here, however, is if you want to have maps that are bigger than 15x15. In this case, you will need an index that is greater than a single byte. If, however, your wall itself is just a single byte, you might end up with, say, a struct that has size 3 (two bytes for the index, one for the wall itself) but alignment of 2; which would mean you would end up with an empty, unused byte for each element of your struct in the heap! Suddenly you are wasting three bytes per element in overhead, which might not justify the used of the sparse technique if your maps have lots of walls. Also, if your game accounts for the possibility of destroying or even building walls, you will get a bigger overhead using this algorithm.
For the walls themselves, there are a bunch of ways to represent them, of course. If you want to use an oo system, then you will probably want to store pointers to the wall class (note that in many higher level languages, the use of pointers is implicit). The advantage of doing so is that you can develop any kinds of wall sub-classes that have their own specific behaviours. For instance, you could have a grate wall that stops movement but not projectiles, or a wall with a niche, where the niche is a container of items, etc. Such system is not, of course, all that space efficient, but at least as far as modern computers go, the space used here is not going to impact the system in any meaningful way, and the ability to easily grow your game is frequently worth it.
An opposite approach has the wall being stored as an id, with different ids being different kinds of walls. As long as you know what you want to do with your walls, such system can be quite workable. For instance, you could have: (0 - no wall, 1 - standard wall, 2 - alternate wall, 3 - wall with niche), etc. By alternate wall, I mean a wall with an alternate artwork (so your walls inside a dungeon don't need to all look the same). It is possible to use this with different artwork for different dungeon types, so you could have 100s of different wall artwork but only two types per dungeon) You could even mix this with a flag system. Since we used only the first two bits in the previous example, we could use the next two for flags (bit 3 - illusory wall flag, bit 4 - wall with switch). So, if a wall had the id 10, we would have an alternate artwork wall with a switch that is really an illusion. Such a system still leaves some room for special walls as well. Note that our flags don't make sense if the first (as in, least significant) two bits are both 0. Thus, we could use these (ids divisible by 4 other than 0) to represent special walls. For instance, id 4 and 8 could be embedded staircases going down or up respectively, while id 12 could be a wall with a door. Note that some of the special cases (niches with items, locked doors, switches) could have their specific data (events for toggling a switch, items in the niche, key id and lockpicking chances) stored in a sparse matrix as well. Since these are usually few, compared to the total walls, the use of a sparse matrix might make more sense here.
Another way to save up on space here is if your maps are square. Since (n+1)n = n(n+1), then if we like in this example only used up to 16 different ids for walls, it would be possible to store in a single byte the id of an horizontal wall in the lower bits and the id of a vertical one in the higher bits. If you are using C or a similar language, the trouble of converting from one matrix type to the other is easily solved by making two separate arrays variables but making them point to the same position in memory.
Of course, you can just have each tile point to four different walls (along the four different cardinal directions). This is usually not a problem unless you are developing your game for a very old system. This allows you to create walls that aren't the same on both sides (which might be a problem for our special walls above, such as having switches or whatnot).
From the game design perspective, I don't much like thick walls because they are way too thick. You don't want to make rooms with too many tiles otherwise your dungeon will be needlessly large and empty. But if a normal room is only between 3x3 to 5x5, having a wall take a whole tile is too much. Furthermore, I think dungeons that have thin walls can account for a more interesting design for their size.