On January 15th, 2020 Microsoft released Edge v79, the first stable version of their Chromium-based Edge web browser.

Location of Microsoft Edge history (v79+)

Windows 7, 8, 10
C:\Users\<username>\AppData\Local\Microsoft\Edge\User Data\Default
C:\Users\<username>\AppData\Local\Microsoft\Edge\User Data\Default\Cache

Format of Microsoft Edge history (v79+)

Bookmarks
Edge Bookmarks are stored in the 'Bookmarks' JSON file.
Cache
Edge Cache is stored using an Index file ('index'), a number of Data Block files ('data_#'), and a number of separate data files ('f_######').
Cookies
Edge Cookies are stored in the 'Cookies' SQLite database, within the 'cookies' table.
Downloads
Edge Downloads are stored in the 'History' SQLite database, within the 'downloads' and 'downloads_url_chains' tables.
Favicons
Edge Favicons are stored in the 'Favicons' SQLite database, within the 'favicons', 'favicon_bitmaps' and 'icon_mapping' tables.
Logins
Edge Logins are stored in the 'Login Data' SQLite database, within the 'logins' table.
Searches
Edge Searches are stored in the 'History' SQLite database, within the 'keyword_search_terms' table. Associated URL information is stored within the 'urls' table.
Session Data
Edge Session Data is stored in the 'Current Session', 'Current Tabs', 'Last Session' and 'Last Tabs' files.
Thumbnails
Edge Thumbnails are stored in the 'Top Sites' SQLite database, within the 'thumbnails' table.
Website Visits
Edge Website Visits are stored in the 'History' SQLite database, within the 'visits' table. Associated URL information is stored within the 'urls' table.

Location of Microsoft Edge history (up to v44)

Windows 10
C:\Users\<username>\AppData\Local\Packages\<package name>\AC\MicrosoftEdge\User\Default\Favorites
C:\Users\<username>\AppData\Local\Packages\<package name>\AC\MicrosoftEdge\User\Default\Recovery
C:\Users\<username>\AppData\Local\Packages\<package name>\AC\MicrosoftEdge\User\Default\DataStore
C:\Users\<username>\AppData\Local\Microsoft\Windows\WebCache

Format of Microsoft Edge history (up to v44)

Bookmarks
Edge Bookmarks are stored in the 'spartan.edb' ESE database, within the 'Favorites' container. Older versions of Edge stored Bookmarks as separate Internet Shortcut (.url) files in the 'Favorites' folder.
Cache
Edge Cache records are stored in the 'WebCacheV01.dat' ESE database, within the 'Content' containers. The cached files are stored as separate files in locations specified within the ESE database.
Cookies
Edge Cookies are stored in the 'WebCacheV01.dat' ESE database, within the 'CookieEntryEx' containers. Older versions of Edge stored cookies as separate text files in locations specified within the ESE database.
Downloads
Edge Downloads are stored in the 'WebCacheV01.dat' ESE database, within the 'iedownload' containers.
Session Data
Edge Session Data is stored in a number of .dat files in the 'Recovery' folder.
Website Visits
Edge Website Visits are stored in the 'WebCacheV01.dat' ESE database, within the 'History' containers.