Elvis was not a songwriter, relying on the material of others for his recordings. This was pretty standard for someone who came to prominence in the mid-1950s, when singers were generally not also meant to be songwriters (this changed in the early 1960s with the rise of The Beatles and Bob Dylan, but that's another story). 'Major label' recording companies, at that point in history, would have an A&R person who was responsible not only for signing the artists and guiding them in the studio but providing the artist with material (A&R stands for 'artists & repertoire', and this is the 'repertoire' part of the equation).

However, Elvis, until 1956, was on a regional minor label in Memphis (Sun Records), rather than a major label, and minor labels were basically family businesses that didn't have to follow industry standards, which meant they were often better able to exploit new trends than the slower major labels, but also that the market was more volatile for them in other ways (minor labels went bankrupt often). Sam Phillips of Sun Records' strategy for getting the right material out of his artists seems to have initially been to look through the material the artist already played rather than to present them with material, and to find something a little different with a strong emotional core, something that was (perhaps over)dramatically dramatised in the film Walk The Line, with Johnny Cash singing 'Folsom Prison Blues' for Phillips.

As such, early Sun Records recordings by Elvis - 'Mystery Train', 'That's All Right', 'Blue Moon Of Kentucky' - are probably a fairly accurate reflection of a side of Elvis's genuine musical personality at the time (though according to biographers like Peter Guralnick in Last Train To Memphis, Elvis's initial recordings for Phillips were sweet country ballads that his mother might like, rather than the R&B-influenced tunes he'd become famous for at Sun - it was only after Elvis loosened up a bit that Phillips heard him sing stuff like that). To modern ears, Elvis's vocals seem fairly unremarkable - they're not as strongly encoded as 'African American' as, say, John Lee Hooker - but that's partly because we're listening to them with modern ears; compare them to the very clipped and 'proper' way that Pat Boone sings songs like 'Tutti Frutti', which was much closer to the dominant way that white people in America sang on commercial recordings at the time, and which is comical today. If Elvis's way of singing sounds unremarkable today it's because Elvis sang it with a naturalness that was shocking at the time, and that naturalness wasn't something that a studio could have told him to do.

Sam Phillips of Sun Records, of course, was famous for saying that if he could find a white boy who sang like a black man, he could make a million dollars. Which is primarily noteworthy because Elvis is now an industry in of itself, and shows him as very perceptive; but according to Guralnick's interviews with Phillips' secretary, the import of Phillips' statement when he was making it was frustration. Phillips was so sure that he was recording a bunch of important music (at this point Phillips was recording blues acts like Howlin' Wolf and leasing them to record labels like Chess) but that basically people were too racist to take it seriously; this is what he was really saying. As the person who had recorded acts like Howlin' Wolf, Phillips was the right person in the right place to understood what he had when Elvis busted out 'That's All Right'. But it was still Elvis who busted out 'That's All Right', if that makes sense.

After Sun, and in Elvis's earlier years with RCA Records (the albums Elvis Presley, Elvis, and Elvis Is Back, and various singles of the era), the assumption I would make is that Elvis still had some say over what songs he recorded and how it sounded until the early 1960s. Elvis was recorded largely backed by his touring band with a touch of commercial sweetening (the backing vocals of the Jordanaires, largely). Steve Sholes, an A&R man at RCA and producer of Elvis's early-ish records, was basically a country music producer. While he was clearly a savvy producer of pop music, rock & roll's success was clearly somewhat mysterious and uncomfortable to many older men in the music industry, who clearly didn't see the appeal themselves. Sholes was, at least initially, in this category. According to Peter Guralnick's Last Train To Memphis, Sholes' reaction to hearing 'That's All Right' (after discovering that it had been very successful) was along the lines of "you've got to be kidding!"

Nonetheless, Sholes was a canny businessman, and he knew that whatever Elvis's appeal was, it was real. He presumably figured that Elvis himself probably had the best idea of the source of his appeal, and was happy enough to push ideas at Elvis and see what the man himself picked. According to Last Train To Memphis:

'ON TUESDAY, JANUARY 10, 1956, two days after his twenty-first birthday, Elvis Presley entered the RCA studio in Nashville for the first time. Just before Christmas Steve Sholes had sent him a brief note proposing ten titles for his consideration, along with acetate demos and lead sheets for each of the songs. The selection included ballads, novelty numbers, country weepers, blues, and “beat” songs, which Sholes urged him to learn and then let the RCA a&r man know which of them he liked best. About a week before the session, at the Variety Club in Memphis, an after-hours “members only” club for entertainment people and businessmen, Elvis sat down at the beat-up old upright and picked out “Heartbreak Hotel” for Dewey, announcing he was going to cut it in Nashville the following week.

In the studio, according to Guralnick, Elvis had a clear idea of what he wanted, and by about mid-1956, Sholes was willing to basically let Presley run the session; nobody at RCA apart from Elvis had really understood the appeal of 'Heartbreak Hotel', Elvis's first big RCA single, but with Elvis so insistent on the song, they had trusted his instinct all the way to the top of the charts. Guralnick goes into some detail about the recording of 'Hound Dog' and 'Don't Be Cruel', both recorded at one session in early July 1956. With 'Hound Dog':

They started with “Hound Dog,” but perhaps not surprisingly it proved more difficult to capture on record than anyone had anticipated from its easy onstage success [it had already been performed on TV by this point]. Engineer Ernie Ulrich, as cynical about rock ’n’ roll as anyone else in the building, got a good sound mix early on, but then there were seventeen takes without a satisfactory master. The drums, always the driving force in the live show, weren’t working right, Scotty was groping toward his guitar solo, the Jordanaires were having some difficulty finding their place, and Shorty Long, the boogie-woogie piano player who had filled in on the last New York session, was just looking for his cues. Steve Sholes was getting visibly discouraged—he was desperate to get material for the second album, and here they were wasting all their time on a single song—but Elvis, who exhibited few points of stillness in any other aspect of his life, maintained absolute concentration. “In his own reserved manner,” wrote Wertheimer, “he kept control, he made himself responsible. When somebody else made a mistake, he sang off-key. The offender picked up the cue. He never criticized anyone, never got mad at anybody but himself. He’d just say, ‘Okay, fellas, I goofed.’ ”

With 'Don't Be Cruel':

Elvis had the song played back for him again and started working it out on the guitar while the others listened for the first time. Then he sketched out a rough arrangement on the piano, which he showed to Shorty Long, who made notes on the lead sheet. By this time he had memorized the lyrics. Scotty tried out a couple of openings, and Elvis suggested that he leave a little more space and told D.J. to “come in behind Scotty and slow it down a little”; then the Jordanaires worked out their arrangement, and after about twenty minutes they were ready for a run-through. After a single rehearsal, Sholes was ready to record, but Elvis wanted to rehearse some more, so they did. The song continued to evolve through twenty-eight takes. It took on a lilting, almost casual, offhand kind of feel, as Scotty virtually sat out except at the beginning and the end, Gordon Stoker of the Jordanaires came to sing a duet with Elvis on the chorus, and D.J. laid Elvis’ leather-covered guitar across his lap and played the back of it with a mallet, to get an additional snare effect. It was hardly a formulaic approach, and it was clearly one that left the nominal a&r director baffled. When they finally got the sound that he was looking for, Elvis pronounced, “That felt good,”...

As these two songs were if anything more successful than 'Heartbreak Hotel', Elvis was, from then on basically allowed to run his own sessions.