Here's a possible approach :
# recreate your input data
vals <- read.table(
text=
"1 4 3 5
9 6 2 6")
map <- read.table(
text=
"1 apple
2 banana
3 toast
4 beer
5 chips
6 cheese
9 wine",stringsAsFactors=F)
names(map) <- c('K','V')
# - turn vals into a vector (using unlist function)
# - get the row indexes of the unlisted keys corresponding 
#   to map keys (using match function)
# - using the indexes select the key names in map (using vector subsetting [])
# - turn the character vector into 2d matrix with original dimension of vals
# - coerce to data.frame
mapped <- as.data.frame(matrix(map$V[match(unlist(vals),map$K)],nrow=nrow(vals)))
# > mapped
# V1     V2     V3     V4
# 1 apple   beer  toast  chips
# 2  wine cheese banana cheese