这是个非常有意义的问题。
一者因为传统记载不可靠，二者「皇」、「帝」这些称号的出现，正是「层累说」的一个极好例子。
先说结论：商周称「王」，而且那个时候「皇」、「帝」这两个字和「君主」意思没半毛钱关系。最早称「帝」的是战国的秦昭王和齐缗王，称「皇帝」的是秦始皇帝，厥后二千年之君主亦皆称皇帝，厎于革命。
商周到秦汉，君主的称号问题就是个烂坑。战国时人就完全搞不清楚了，遑论司马迁的《史记》。比如按《史记》的记载，商朝是称「帝」的，但「帝」明显比「王」高级，周为什么又只称「王」？所以只好口胡了一个「於是周武王為天子。其後世貶帝號，號為王。」的说法，糊弄过去。
p.s.《史记》有 1000 个错误也不影响其伟大。(^_^*)
〇.传统记载
先概述一下传统记载里的上古帝王，我随便取一种儒家的排法：
1.六十四民
2.九皇（神农、伏羲等）
3.五帝（黄帝、帝颛顼、帝喾、帝尧、帝舜）
4.三王（夏、商、周）
道家也有自己的排法，不过神奇的多。说先是盘古时代，然后太上老君给了三皇每人一本真经，于是他哥仨各治理天下三十六万年。之后九亿九千九百九十九万年，才是五帝的世界。五帝各治理天下三万六千年，之后又是新三皇，五龙氏，新盘古，再才是伏羲、隧人、祝融、神农、黄帝。这比地球寿命都长。（并没有( ´▽｀)）
「尧舜禹」的问题见这个回答：
下面依次讨论商周以来「王」、「帝」、「皇帝」这些称号的来源问题。
一.「王」
商周称「王」，于甲骨卜辞、铜器铭文皆有明征。《史记》里记载商称「帝」，周称「王」，此说有误。至于司马迁为什么会认为商王称「帝」，下节将会讨论。
林沄先生云「王」字象斧钺之形，此说已甚普遍，不烦赘述。下图一看便知：
甲骨文之「王」则形颇简省：
斧钺在古代既是武器，又是刑具，所以用「王」字代表军事领袖，是很自然的。周武王讨伐商纣，于商郊牧野，就左仗黄钺（《牧誓》）指挥军队。这种习惯一直保留到很晚，刘备赐关羽「假节钺」，故得以专征伐。
商周之际，最高首领就是称「王」。周文王、还有周文王的父亲——就是《诗经》里常提到的「王季」，都称「王」，而那个时候周不过只是商王朝西边的一个小邦。但在后代「大一统」思想的影响下，大家总觉得天下只能有一个王，所以司马迁在《史记》中把「王季」改称为「公季」，认为彼时周国只能称「公」，不能称「王」，「王季」是后代追封的。
西周小国称王的现象也是常见的，出土的「芈伯簋」铭文里，就有一个「武芈幾王」。春秋时的楚国、吴国、越国君主也称「王」，到了战国，王室日卑，各国君主也慢慢开始称「王」了。不过这样一来，通货膨胀，「王」也就不值钱了。
这就有了我们接下来讨论的「帝」。
二.「帝」
「帝」是个大问题。
1.传统文献中的「帝」
先看传世文献里「帝」的意思，传世文献以《诗经》、《尚书》（今文 28 篇）为最古，亦最可信。不多废话，直接上数据：
《诗经》里的「帝」：
胡然而天也，胡然而帝也。《君子偕老》
有皇上帝，伊誰云憎。《正月》
上帝甚蹈，無自暱焉。/ 上帝甚蹈，無自瘵焉。《菀柳》
有周不顯，帝命不時。/ 文王陟降，在帝左右。/ 上帝既命，侯于周服。/ 殷之未喪師，克配上帝。《文王》
昭事上帝，聿懷多福。/ 上帝臨女，無貳爾心。《大明》
皇矣上帝，臨下有赫。/ 上帝耆之，憎其式廓。/ 帝遷明德，串夷載路。/ 帝省其山，柞棫斯拔，松柏斯兌。/ 帝作邦作對，自大伯王季。/ 維此王季，帝度其心，貊其德音。/ 既受帝祉，施于孫子。/ 帝謂文王，無然畔援，無然歆羨，誕先登于岸。/ 帝謂文王，予懷明德，不大聲以色，不長夏以革。/ 不識不知，順帝之則。/ 帝謂文王，詢爾仇方，同爾兄弟，以爾鉤援，與爾臨衝，以伐崇墉。《皇矣》
履帝武敏歆，攸介攸止。/ 以赫厥靈，上帝不寧。/ 其香始升，上帝居歆。《生民》
上帝板板，下民卒癉。《板》
蕩蕩上帝，下民之辟。/ 疾威上帝，其命多辟。/ 匪上帝不時，殷不用舊。《荡》
后稷不克，上帝不臨。/ 昊天上帝，則不我遺。/ 昊天上帝，寧俾我遯。/ 昊天上帝，則我不虞。《云汉》
不顯成康，上帝是皇。《執競》
貽我來牟，帝命率育。《思文》
明昭上帝，迄用康年。《臣工》
上帝是依，無災無害。/ 無貳無虞，上帝臨女。/ 皇皇后帝，皇祖后稷。《閟宮》
古帝命武湯，正域彼四方。《玄鸟》
幅隕既長，有娀方將，帝立子生商。/ 帝命不違，至于湯齊。/ 昭假遲遲，上帝是祗，帝命式于九圍。《長發》
《尚书》（排除战国伪托的《虞夏书》）里的「帝」：
予畏上帝，不敢不正。《汤誓》
肆上帝將復我高祖之德。《盘庚》
帝乃震怒，不畀『洪範』九疇，彝倫攸斁。《洪范》
乃命于帝庭，敷佑四方。《金滕》
予惟小子，不敢替上帝命。/ 爽邦由哲，亦惟十人迪知上帝命越天棐忱。《大诰》
聞于上帝，帝休，天乃大命文王。《康诰》
自成湯咸至于帝乙。《酒诰》
皇天上帝改厥元子茲大國殷之命。/ 王來紹上帝，自服于土中。《召诰》
敕殷命終于帝。/ 上帝引逸，有夏不適逸；則惟帝降格，向于時夏。弗克庸帝，大淫泆有辭。/ 爾殷多士，今惟我周王丕靈承帝事，有命曰：割殷，告敕于帝。《多士》
我亦不敢寧于上帝命。/ 在太戊，時則有若伊陟、臣扈，格于上帝。/ 在昔上帝割申勸寧王之德，其集大命于厥躬。/ 乃惟時昭文王迪見冒，聞于上帝。《君奭》
洪惟圖天之命，弗永寅念于祀，惟帝降格于夏。/ 乃大淫昏，不克終日勸于帝之迪，乃爾攸聞。/ 厥圖帝之命，不克開于民之麗，乃大降罰，崇亂有夏。/ 以至于帝乙，罔不明德慎罰，亦克用勸。《多方》
古之人迪惟有夏，乃有室大競，籲俊尊上帝迪，知忱恂于九德之行。/ 亦越成湯陟，丕釐上帝之耿命。/ 帝欽罰之，乃伻我有夏，式商受命，奄甸萬姓。/ 以敬事上帝。/《立政》
用端命于上帝。《康王之誥》
皇帝清問下民鰥寡有辭于苗。/ 上帝不蠲，降咎于苗。《吕刑》
惟時上帝，集厥命于文王。《文侯之命》
《诗经》出现「帝」的诗共 16 首，「帝」字出现 43 次。其中「上帝」出现 24 次，过「帝」字之半。其他「帝」字，细审文意，亦都是指「上帝」。故《诗经》中之「帝」完全等同于「上帝」。
《尚书》出现「帝」篇目共 15 篇，「帝」字出现 33 次。其中「上帝」出现 18 次，亦过「帝」字之半。谛厥文，其他「帝」字亦都指「上帝」，只有两个例外，就是《酒诰》和《多方》中各出现了一次「帝乙」，指的是商朝的先王。
我们似乎可以下断言：「帝」就是指「上帝」，其本义与「帝王」毫无关系。
但「帝乙」这个「实验误差」却如鲠在喉，不过我们下面将会解决这个问题。
2.出土文献中的「帝」
再看出土文献中的「帝」。
「帝乙」在「必其卣」铭文里也有：
商王名冠以「帝」的称呼，甲骨文里就更多了：
比如武丁称「帝丁」、祖甲称「帝甲」、康丁称「帝丁」等等，emmmm……好像商王确实可以称「帝」的……
我们刚刚下的结论，摇摇欲坠。
但是，日本学者岛邦男发现，这个「帝」不是「帝王」之意，而是儿子对父亲的称呼。
不过岛邦男的话也有一定的问题。事实上，甲骨卜辞中，商王只称直系父王为「帝」，而叔叔伯伯里做过商王的从不称「帝」。比如祖庚是康丁的伯伯，其后代也没有当王的，卜辞里就绝无「帝庚」的说法。「帝」的这种称法明显区分了「直系」与「旁系」，故裘锡圭先生云：「称父为「帝」跟区分嫡庶的观念显然是有联系的」[1]。这种用法在金文里也有，比如称父亲为「帝考」。
所以这里的「帝」就是后代所谓「嫡庶」的「嫡」的前身。「嫡」的右边是「啻」，「啻」从「帝」声，判定它们是同源的是没有问题的。
《史记》误将这些「帝」理解为「帝王」，故认为商王称「帝」，明显是受了「帝」在后世的词义影响。
《春秋》里记载：「夏五月乙酉，禘于莊公。」是鲁闵公祭其父。「禘祭」的「禘」自也暗承这种古老的用法。
3.「帝」词义的演变
根据上文，我们知道了「帝」的两种用法：卜辞中用作直系先王之称，《诗经》《尚书》中用为「上帝」之专称。这两种用法显然是有联系的。
商周称神为「上帝」，正是因他们认为自己是「上帝」的嫡系后代。
甲骨卜辞中商王祭祀的「高祖猱」，王国维等认为即《史记》中的帝喾，《山海经》中的帝俊，亦即帝舜，此三者实乃一帝之分化，商人认为自己是帝喾或帝舜的后代。另外还有周人祖黄帝，楚人祖帝颛顼，姜姓祖炎帝，嬴姓祖少皞，等等。《上博简》更是直接宣称夏商周的始祖是天帝之子。
这些「上帝」之间，本来毫不相干，但在春秋之际，民族彼此交融，终于慢慢人格化，成为一个个实在的「上古帝王」，甚至有了血缘关系，也就是战国颇爱称道的「五帝」。于是「帝」这个字也有了「帝王」之意，成了比「王」还要高一等的称呼。这个变化至迟在春秋末、战国初就有了，《孟子》里就经常讲帝舜的八卦，不过「五帝」体系的出现还要更晚一点。
到了战国中晚期，秦国和齐国并驱争先，雄于诸国。终于他们再也瞧不上「王」这个称呼了，公元前 288 年，秦昭王称「西帝」，齐缗王称「东帝」。
不过在舆论的压力下，他俩过了几个月「称帝」的瘾后，又改回「王」就是了。
p.s.「帝」和「蒂」没有关系。
以下引 @布之道 说：
「蒂」原来作「蔕」，是「帶」声字，中古时期「帶」由于音形皆近才又不少写作「帝」了的。
三.「皇」
「皇」字的历程和「帝」差不多。
先看文献：
有皇上帝，伊谁云憎。《诗·小雅·正月》。
献之皇祖。《诗·小雅·信南山》。
皇尸载起。《诗·小雅·楚茨》。
皇矣上帝，临下有赫。《诗·大雅·皇矣》。
皇王惟辟，皇王烝哉。《诗·大雅·文王有声》。
肆皇天弗尚。《诗·大雅·抑》。
无忝皇祖。《诗·大雅·瞻印》。
燕及皇天。/ 假哉皇考。《诗·周颂·雍》。
於乎皇考。/ 於乎皇王。/ 念兹皇祖。《诗·周颂·闵予小子》。
休矣皇考。《诗·周颂·访落》。
皇皇后帝。皇祖后稷。周公皇祖。《诗·鲁颂·宫》。
皇天既付中国民越厥疆土于先王。《书·梓材》。
皇天上帝改厥元子。/ 其自时配皇天。《书·召诰》。
时则有若伊尹格于皇天。《书·君奭》。
皇天改大邦殷之命。/ 皇天用训厥道。/ 皇后凭玉几。《书·顾命》。
皇帝哀矜庶戮之不辜。/ 皇帝清问下民。《书·吕刑》。
很明显，「皇」就是个形容词，常用在「天」「帝」「祖」「考」这类词前面，大致可翻译为「光明的 / 伟大的」的意思。这个时候的「皇」，没有任何「君主」的意思在里面，也从来没有名词的用法。
但本来表示至上神的「帝」字，已被用作古帝王的称号了，其奈神何？为了找一个逼格更高的词来称呼神，人们选中了「皇」。原因很简单——「皇」经常和「天」啊、「帝」啊连用，比如上引《诗经》的「有皇上帝」、「皇矣上帝」、「皇皇后帝」。
「皇」由形容词变成名词这种现象，最早可能发生于楚地，《楚辞》里有「东皇太一」，又有「西皇」（是不是和齐秦自称的「东帝」、「西帝」对应得很好～）——从此「皇」成为了神的代称。
但好景不长，「皇」被捧成至高神之后，跟「帝」一样，也开始了人格化的趋势，逐渐变成了「五帝」以前的「上·上古帝王」，也就是「三皇」（或「九皇」）。这种变化和「帝」字是完全平行的。
不过这种变化发生得很晚，导致「皇」的人格化还没有完成的时候，秦国便统一了。而「祖述尧舜」这种本是乱世时游士常用的说辞，统一后瞬间就没了动力。所以「三皇」的说法有很多种，也保留着相当的神话色彩。比如女娲造人、神农尝百草，都是「人格化」走到一半被强制终结的结果。相反，「五帝」的神话色彩就小很多。
四.「皇帝」
「皇帝」的来源有官方背书：
丞相綰、御史大夫劫、廷尉斯等皆曰：「昔者五帝地方千里，其外侯服夷服諸侯或朝或否，天子不能制。今陛下興義兵，誅殘賊，平定天下，海內為郡縣，法令由一統，自上古以來未嘗有，五帝所不及。臣等謹與博士議曰：『古有天皇，有地皇，有泰皇，泰皇最貴。』臣等昧死上尊號，王為『泰皇』。命為『制』，令為『詔』，天子自稱曰『朕』。」王曰：「去『泰』，著『皇』，采上古『帝』位號，號曰『皇帝』。他如議。」《史记·秦始皇本纪》
这段话意思很明白，秦始皇取了「泰皇」的「皇」，和「上古帝号」的「帝」，称为「皇帝」。平行的事件是，项羽取了「五霸」的「霸」，和「三王（夏商周）」的「王」，自称「霸王」。都是发明词汇的小能手。
从此中国二千年之帝王，便都称作「皇帝」了。
谥号：
至于题主说汉朝君主称「帝」，如「汉文帝」、「汉武帝」，则是「汉孝文皇帝」、「汉孝武皇帝」的简称。其中的「文」、「武」，是大臣们对已故君王的「盖棺定论」，也就是所谓的「谥号」。
「谥号」作为一种评定，自然有好有恶。春秋时的楚共王，临死前良心发现，跟大臣们说：「你们给我谥个「灵」或者「厉」我就满意了！」——「灵」「厉」显然是「恶谥」。不过大臣最终还是给了个不错的谥号——「共」。
楚子疾，告大夫曰：「不穀不德，少主社稷，生十年而喪先君，未及習師保之教訓，而應受多福，是以不德，而亡師于鄢，以辱社稷，為大夫憂，其弘多矣，若以大夫之靈，獲保首領，以歿於地，唯是春秋窀穸之事，所以從先君於禰廟者，請為靈若厲，大夫擇焉。」莫對，及五命，乃許，秋，楚共王卒，子囊謀諡，大夫曰：「君有命矣。」子囊曰：「君命以共，若之何毀之，赫赫楚國，而君臨之，撫有蠻夷，奄征南海，以屬諸夏，而知其過，可不謂共乎，請謚之共。」大夫從之。《左传·襄 13》
秦始皇对这种「子议父、臣议君」的行为特别反感，所以取消了谥号，自称为「始皇帝」，其子为「二世皇帝」，乃至子子孙孙无穷。但想法很美好，现实很残酷。秦朝二世而亡，于是汉朝又恢复了谥号。
制曰：「朕聞太古有號毋謚，中古有號，死而以行為謐。如此，則子議父，臣議君也，甚無謂，朕弗取焉。自今已來，除謚法。朕為始皇帝。後世以計數，二世三世至于萬世，傳之無窮。」《史记·秦始皇本纪》
「谥号」一直沿用到了清朝，不过越来越不客观就是了。
庙号：
所谓「某祖」、「某宗」为庙号，是对皇族内部祭祀而言的。按理说，只有功德高盛的皇帝才能有庙号。就像申屠嘉所言：
功莫大於高皇帝，德莫盛於孝文皇帝。高皇帝廟，宜為帝者太祖之廟；孝文皇帝廟，宜為帝者太宗之廟。
说得很清楚，汉高祖有混一海内之功，汉文帝有仁恕恭俭之德，故奉高皇帝为太祖，汉文帝为太宗。
但到了讨论汉武帝庙号的时候，夏侯胜就认为武帝虽有攘夷之功，但耗斁民力，还搞奢侈腐化，不太行：
長信少府夏侯勝獨曰：「武帝雖有攘四夷、廣土境之功，然多殺士眾，竭民財力，奢泰無度，天下虛耗，百姓流離，物故者半，蝗蟲大起，赤地數千里，或人民相食，畜積至今未復；無德澤於民，不宜為立廟樂。」
不过最后大家还是给汉武帝立了庙，称为「世宗」。
所以汉朝称「宗」还是很严格的，不是每个皇帝都能混出个庙号。
然而「通货膨胀」的事情永远都在发生，往后每个皇帝都有庙号了，谥号也越来越臭长，越来越不靠谱。李世民最初还是「文皇帝」，到了后来就变成了「文武大聖大廣孝皇帝」，宋太祖谥号「启运立极英武睿文神德圣功至明大孝皇帝」，这就完全没法叫。所以只好用庙号来称呼他们了，这就有了唐太宗，宋太祖的叫法。
一切的一切，
都怪通货膨胀。