How does the brain learn what something is for the first time?
According to current models of human concept learning, the answer to your question is both. 

Think of a simplified domain in which every object consists of only several features, and therefore can be visualized as a point in some multidimensional feature space. For example, the features that define objects might be its size, shape, color, and weight. Furthermore imagine that objects tend to be clustered throughout this space according to what category they belong to, because members of the same category are generated by the same natural process. 

So based on current models, a novel stimulus is compared to existing concepts and is either placed into the concept (cluster) that it's closest to, or if it's insufficiently close to any existing concept, then a new concept will be created. This is the basic idea of current Bayesian theories such as the Rational Model, which treats human category learning as a problem of probability density estimation, and its contenders such as  SUSTAIN. 

Here's a video lecture by Josh Tenenbaum, a leading researcher in both machine learning and cognitive science, in which he gives an excellent introduction to a number of these issues and many more.