Sam & Max's relationship
Sam and Max have been best friends since their early childhood. Their past selves are always shown hanging out together, such as in Terror on the Tanbark and Chariots of the Dogs, and in commemorative photos in the office, one of which shows them taking a bath as children. And in the "character bios" listed on the Sam & Max Season One compilation, it says "these guys have known each other all their lives".
It's not clear exactly when and how they decided to become Freelance Police, but given their shared history getting the same job was probably obvious. The same can be said about their decision to live in the same house.
Even on the job, Sam and Max never willingly split up for more than a moment. When forcibly separated, they tend to become unable to function properly and obsessed with reuniting as soon as possible. Examples of this would be Monkeys Violating the Heavenly Temple, Bad Day on the Moon, A Glitch in Time, Culture Shock, What's new, Beelzebub? (When Sam enters his personal hell) and They Stole Max's Brain!. Even in Sam & Max Hit the Road where you have to free Max from a dunk tank, you can leave the area but Sam refuses to do certain things because Max isn't with him ("It just wouldn't be romantic without Max").
In Culture Shock, anytime Sam clicks on a usable object (other than a passageway/character) after Max is kidnapped by Brady Culture, he will mention a comment referring to Max (this comment is cycled). In They Stole Max's Brain!, Sam turns into "Noir Sam"; he goes as far as threatening a The C.O.P.S. member due to how she fails to help Sam find Max's lobotomizing device.
Max is generally content to let Sam take the lead and figure out what to do next. In turn, Sam accepts Max's occasional suggestions more often than would be wise. He even agreed that Max should be the one to run for president because Sam got to answer the phone.
Sam has used Max as a weapon more than a few times, often threatening that he "[knows] how to use this!" Max doesn't seem to mind, and when Sam asked how he felt about being used as a club, he replied that it was "oddly refreshing". In Hit the Road, Max is in Sam's inventory box and can be used as an item.
Sam and Max are at times insensitive or downright insulting to one another. However, aside from the occasional snappy comeback or threat of bodily harm, neither of them seem to be bothered by this. It's a bit unclear how seriously such threats should be taken, but they work: the two like and respect each other enough that they never have any serious fights. Fights over things like who gets to pick up the phone are a different matter however.
 More than just friends?
There have been many instances of apparent romantic subtext between Sam and Max, generally in the service of a joke, ala Jay & Silent Bob. They were seen in wedding attire twice, once on Steve Purcell's wedding cake, with Max as the bride, and once in the animated series, with Sam as the bride. In Season 1, Sybil will also make a suggestion if you choose both Max & the wedding cake in Sam's dream, and Sybil's match making "computer" says that their perfect soulmate is each other. Wedding attire is also available for both to wear in Sam & Max Hit the Road's dress-up game, in which Max is the bride. There is quite a lot innuendo in the animated series, such as the "Grab me by the ears!" "You are aware there are children watching" exchange in Max's Big Day. Or when Sam slaps Max, "Hit me again Sam, I like it!" In The Trouble with Gary Max states "at times like these, Sam and I have a special way of letting the other know how we feel about each other!" It also exists in the Telltale games, such as when Sam and Max discuss Max's habit of hitting Sam early in the morning, with Max saying that "it's his way of showing affection", and when Sam wishes he would stop doing it before 6 AM, Max says "I could never stop loving you, Sam." in Moai Better Blues, and Max's suggestion that they may be their own parents in Chariots of the Dogs. In the episode 'Kiss Kiss, Bang Bang', Max expresses a somewhat jealous/annoyed tone when Sam seemingly flirts with the receptionist, Ms. Honey Bunny, and is also annoyed/jealous when Ms. Honey Bunny winks at Sam, saying "You really should have that twitch looked at!" and intervenes between the two. In the animated series, Sam & Max became the surrogate parents of a baby Crocodile, raising it as a child instead of a pet. In The Penal Zone (first episode of season 3), when Sam finds an engagement ring on the floor, Max says "Sam, this is all so sudden. I don't know what to say." If you use the ring on Max, you'll get a cutscene that parodies Debeers jewelry commercials.
But as many romantic jokes as there are, there are also many lines that say otherwise. In their more serious moments, Sam and Max are often dismissive of the idea. Examples of these times could be seen in Abe Lincoln Must Die!, when Sybil's match making machine said that Sam and Max were soulmates, which Sam described as "another blow to the idea of a fair and just universe." When Sybil called them Luddites and Max angrily responded that they were just very good friends. In addition, Max expressed fear at the possibility of seeing Sam naked in the webcomic The Big Sleep.
It is also notable that Max is usually the one who voices the questionable comments. It's not unusual for him to have lapses of judgment and say things that can actually be more innocent than they sound, often embarrassing Sam in the process. For example, in What's new, Beelzebub? he asked Sybil if her marriage to Abe was a shotgun wedding, which offended her until she realized that he didn't know what that meant.
Despite having them on his wedding cake, Steve Purcell dismissed the idea of making Max a girl in the animated series, although in Tonight We Love Max dresses up as Sam's date to get into a couple's only theme park. Also, according to the production commentary of Night of the Raving Dead, he requested not to have them grinding on the dance floor.